Little Cyan Fish har en følge av ikke-negative heltall $a_1,a_2,\ldots,a_n$ med lengde $n$ i hånden. Little Cyan Fish kan utføre følgende operasjon så mange ganger han vil:

• Velg et heltall $1 \le i \le n$.
• Endre $a_i$ til $\operatorname{mex}_{1\le k<i}a_k$.

Her, for en mengde av ikke-negative heltall $S$, er notasjonen $\operatorname{mex} S$ definert som det minste ikke-negative heltallet som ikke forekommer i mengden $S$. For eksempel er $\operatorname{mex}\{0,1,2,4,6\}=3$, $\operatorname{mex}\{1,2,3\}=0$, $\operatorname{mex}\varnothing=0$.

Little Cyan Fish ønsker å gjøre verdien til $a_n$ så stor som mulig gjennom et visst antall operasjoner (muligens 0). Little Cyan Fish vil at du skal beregne:

1. Hva som er den maksimale mulige verdien til $a_n$ etter et hvilket som helst antall operasjoner;
2. På grunnlag av at 1 er oppfylt, hva som er det minste antallet operasjoner som kreves for å oppnå denne maksimale verdien.

Input

Det er flere testtilfeller. Den første linjen i inndataene inneholder ett enkelt heltall $T$ ($1 \le T$), som angir antall testtilfeller.

For hvert testtilfelle inneholder den første linjen i inndataene et heltall $n$ ($1 \le n \le 10^6$), som representerer lengden på følgen.

Den neste linjen inneholder $n$ heltall $a_1,a_2,\ldots,a_n$ ($0 \le a_i \le 10^9$).

Det er garantert at summen av $n$ over alle testtilfeller ikke overstiger $10^6$.

Output

For hvert testtilfelle, skriv ut én enkelt linje med to heltall. Det første heltallet representerer den maksimale verdien til $a_n$, og det andre heltallet representerer det minste antallet operasjoner som kreves.

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