Little Cyan Fish memiliki barisan bilangan bulat nonnegatif $a_1,a_2,\ldots,a_n$ sepanjang $n$. Little Cyan Fish dapat melakukan operasi berikut sebanyak berapa pun kali:

• Pilih sebuah bilangan bulat $1 \le i \le n$.
• Ubah $a_i$ menjadi $\operatorname{mex}_{1\le k<i}a_k$.

Di sini, untuk himpunan bilangan bulat nonnegatif $S$, notasi $\operatorname{mex} S$ didefinisikan sebagai bilangan bulat nonnegatif terkecil yang tidak terdapat dalam himpunan $S$. Misalnya, $\operatorname{mex}\{0,1,2,4,6\}=3$, $\operatorname{mex}\{1,2,3\}=0$, $\operatorname{mex}\varnothing=0$.

Little Cyan Fish ingin membuat nilai $a_n$ sebesar mungkin melalui sejumlah operasi (mungkin 0). Little Cyan Fish ingin kamu menghitung:

1. Nilai maksimum yang mungkin dari $a_n$ setelah sejumlah operasi berapa pun;
2. Dengan memenuhi poin 1, jumlah operasi minimum yang diperlukan untuk mencapai nilai maksimum tersebut.

Masukan

Ada beberapa kasus uji. Baris pertama masukan berisi sebuah bilangan bulat $T$ ($1 \le T$), yang menyatakan banyaknya kasus uji.

Untuk setiap kasus uji, baris pertama berisi sebuah bilangan bulat $n$ ($1 \le n \le 10^6$), yang menyatakan panjang barisan.

Baris berikutnya berisi $n$ bilangan bulat $a_1,a_2,\ldots,a_n$ ($0 \le a_i \le 10^9$).

Dijamin bahwa jumlah $n$ untuk seluruh kasus uji tidak melebihi $10^6$.

Keluaran

Untuk setiap kasus uji, keluarkan satu baris berisi dua bilangan bulat. Bilangan pertama menyatakan nilai maksimum $a_n$, dan bilangan kedua menyatakan jumlah operasi minimum yang diperlukan.

Contoh

Masukan 1

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

Keluaran 1

114514 0
2 1
3 2
5 3