Little Cyan Fish har en talföljd av icke-negativa heltal $a_1,a_2,\ldots,a_n$ av längd $n$ i sin hand. Little Cyan Fish kan utföra följande operation valfritt antal gånger:

• Välj ett heltal $1 \le i \le n$.
• Ändra $a_i$ till $\operatorname{mex}_{1\le k<i}a_k$.

Här definieras beteckningen $\operatorname{mex} S$, för en mängd av icke-negativa heltal $S$, som det minsta icke-negativa heltal som inte förekommer i mängden $S$. Till exempel är $\operatorname{mex}\{0,1,2,4,6\}=3$, $\operatorname{mex}\{1,2,3\}=0$, $\operatorname{mex}\varnothing=0$.

Little Cyan Fish vill göra värdet på $a_n$ så stort som möjligt genom något antal operationer (möjligen 0). Little Cyan Fish vill att du beräknar:

1. Vad som är det största möjliga värdet på $a_n$ efter valfritt antal operationer;
2. Under förutsättning att 1 uppfylls, vad som är det minsta antalet operationer som krävs för att uppnå detta maximala värde.

Input

Det finns flera testfall. Den första raden i indata innehåller ett enskilt heltal $T$ ($1 \le T$), som anger antalet testfall.

För varje testfall innehåller den första raden i indata ett heltal $n$ ($1 \le n \le 10^6$), som representerar talföljdens längd.

Nästa rad innehåller $n$ heltal $a_1,a_2,\ldots,a_n$ ($0 \le a_i \le 10^9$).

Det garanteras att summan av $n$ över alla testfall inte överstiger $10^6$.

Output

För varje testfall, skriv ut en enskild rad med två heltal. Det första heltalet representerar det maximala värdet på $a_n$, och det andra heltalet representerar det minsta antalet operationer som krävs.

Examples

Input 1

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

Output 1

114514 0
2 1
3 2
5 3