Pikku syaanikalalla on kädessään pituutta $n$ oleva ei-negatiivisten kokonaislukujen jono $a_1,a_2,\ldots,a_n$. Pikku syaanikala voi suorittaa seuraavan operaation kuinka monta kertaa tahansa:

• Valitse kokonaisluku $1 \le i \le n$.
• Muuta $a_i$ arvoksi $\operatorname{mex}_{1\le k<i}a_k$.

Tässä ei-negatiivisten kokonaislukujen joukolle $S$ merkintä $\operatorname{mex} S$ määritellään pienimmäksi ei-negatiiviseksi kokonaisluvuksi, joka ei esiinny joukossa $S$. Esimerkiksi $\operatorname{mex}\{0,1,2,4,6\}=3$, $\operatorname{mex}\{1,2,3\}=0$, $\operatorname{mex}\varnothing=0$.

Pikku syaanikala haluaa tehdä luvun $a_n$ arvosta mahdollisimman suuren jollakin määrällä operaatioita (mahdollisesti 0). Pikku syaanikala haluaa sinun laskevan:

1. Mikä on suurin mahdollinen luvun $a_n$ arvo minkä tahansa operaatiomäärän jälkeen;
2. Ehdon 1 täyttyessä, mikä on pienin tarvittava operaatioiden määrä tämän suurimman arvon saavuttamiseksi.

Input

Syötteessä on useita testitapauksia. Syötteen ensimmäinen rivi sisältää yhden kokonaisluvun $T$ ($1 \le T$), joka ilmaisee testitapausten lukumäärän.

Jokaisessa testitapauksessa syötteen ensimmäinen rivi sisältää kokonaisluvun $n$ ($1 \le n \le 10^6$), joka esittää jonon pituutta.

Seuraava rivi sisältää $n$ kokonaislukua $a_1,a_2,\ldots,a_n$ ($0 \le a_i \le 10^9$).

On taattu, että lukujen $n$ summa yli kaikkien testitapausten on enintään $10^6$.

Output

Tulosta jokaiselle testitapaukselle yksi rivi, jolla on kaksi kokonaislukua. Ensimmäinen kokonaisluku esittää luvun $a_n$ suurinta arvoa ja toinen kokonaisluku pienintä tarvittavaa operaatioiden määrää.

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