Litli blágræni fiskurinn er með óneikvæða heiltólnarunu $a_1,a_2,\ldots,a_n$ af lengd $n$ í höndunum. Litli blágræni fiskurinn getur framkvæmt eftirfarandi aðgerð hversu oft sem er:

• Velja heiltölu $1 \le i \le n$.
• Breyta $a_i$ í $\operatorname{mex}_{1\le k<i}a_k$.

Hér, fyrir mengi óneikvæðra heiltalna $S$, er rithátturinn $\operatorname{mex} S$ skilgreindur sem minnsta óneikvæða heiltalan sem kemur ekki fyrir í menginu $S$. Til dæmis er $\operatorname{mex}\{0,1,2,4,6\}=3$, $\operatorname{mex}\{1,2,3\}=0$, $\operatorname{mex}\varnothing=0$.

Litli blágræni fiskurinn vill gera gildið á $a_n$ eins stórt og mögulegt er með einhverjum fjölda aðgerða (mögulega 0). Litli blágræni fiskurinn vill að þú reiknir:

1. Hvert er hæsta mögulega gildið á $a_n$ eftir hvaða fjölda aðgerða sem er;
2. Á grundvelli þess að uppfylla 1, hver er lágmarksfjöldi aðgerða sem þarf til að ná þessu hámarksgildi.

Input

Það eru mörg prófunartilvik. Fyrsta línan í inntakinu inniheldur eina heiltölu $T$ ($1 \le T$), sem gefur til kynna fjölda prófunartilvika.

Fyrir hvert prófunartilvik inniheldur fyrsta línan í inntakinu heiltölu $n$ ($1 \le n \le 10^6$), sem táknar lengd rununnar.

Næsta lína inniheldur $n$ heiltölur $a_1,a_2,\ldots,a_n$ ($0 \le a_i \le 10^9$).

Tryggt er að summan af $n$ yfir öll prófunartilvik fari ekki yfir $10^6$.

Output

Fyrir hvert prófunartilvik skal prenta eina línu með tveimur heiltölum. Fyrri heiltalan táknar hámarksgildið á $a_n$ og seinni heiltalan táknar lágmarksfjölda aðgerða sem þarf.

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