Little Cyan Fish hat eine Folge nichtnegativer ganzer Zahlen $a_1,a_2,\ldots,a_n$ der Länge $n$. Little Cyan Fish kann die folgende Operation beliebig oft ausführen:

• Wähle eine ganze Zahl $1 \le i \le n$.
• Ändere $a_i$ zu $\operatorname{mex}_{1\le k<i}a_k$.

Dabei ist für eine Menge nichtnegativer ganzer Zahlen $S$ die Schreibweise $\operatorname{mex} S$ als die kleinste nichtnegative ganze Zahl definiert, die nicht in $S$ vorkommt. Zum Beispiel gilt $\operatorname{mex}\{0,1,2,4,6\}=3$, $\operatorname{mex}\{1,2,3\}=0$, $\operatorname{mex}\varnothing=0$.

Little Cyan Fish möchte den Wert von $a_n$ durch eine gewisse Anzahl von Operationen (möglicherweise 0) so groß wie möglich machen. Little Cyan Fish möchte, dass du Folgendes berechnest:

1. Den größtmöglichen Wert von $a_n$ nach einer beliebigen Anzahl von Operationen;
2. Unter Einhaltung von Punkt 1 die kleinste Anzahl von Operationen, die zum Erreichen dieses Maximalwerts nötig ist.

Eingabe

Es gibt mehrere Testfälle. Die erste Eingabezeile enthält eine ganze Zahl $T$ ($1 \le T$), die Anzahl der Testfälle.

Für jeden Testfall enthält die erste Zeile eine ganze Zahl $n$ ($1 \le n \le 10^6$), die Länge der Folge.

Die nächste Zeile enthält $n$ ganze Zahlen $a_1,a_2,\ldots,a_n$ ($0 \le a_i \le 10^9$).

Es wird garantiert, dass die Summe von $n$ über alle Testfälle höchstens $10^6$ beträgt.

Ausgabe

Gib für jeden Testfall eine Zeile mit zwei ganzen Zahlen aus. Die erste ist der maximale Wert von $a_n$, die zweite die kleinste erforderliche Anzahl von Operationen.

Beispiele

Eingabe 1

4
2
0 114514
3
0 1 0
4
3 1 2 0
6
6 5 4 3 2 1

Ausgabe 1

114514 0
2 1
3 2
5 3