Little Cyan Fish có một dãy số nguyên không âm $a_1,a_2,\ldots,a_n$ độ dài $n$. Little Cyan Fish có thể thực hiện thao tác sau một số lần tùy ý:

• Chọn một số nguyên $1 \le i \le n$.
• Đổi $a_i$ thành $\operatorname{mex}_{1\le k<i}a_k$.

Ở đây, với một tập số nguyên không âm $S$, ký hiệu $\operatorname{mex} S$ được định nghĩa là số nguyên không âm nhỏ nhất không xuất hiện trong tập $S$. Ví dụ, $\operatorname{mex}\{0,1,2,4,6\}=3$, $\operatorname{mex}\{1,2,3\}=0$, $\operatorname{mex}\varnothing=0$.

Little Cyan Fish muốn làm cho giá trị của $a_n$ lớn nhất có thể thông qua một số thao tác (có thể là 0). Little Cyan Fish muốn bạn tính:

1. Giá trị lớn nhất có thể của $a_n$ sau một số thao tác tùy ý;
2. Với điều kiện thỏa mãn mục 1, số thao tác ít nhất cần thực hiện để đạt giá trị lớn nhất đó.

Dữ liệu vào

Có nhiều bộ kiểm thử. Dòng đầu tiên của dữ liệu vào chứa một số nguyên $T$ ($1 \le T$), cho biết số bộ kiểm thử.

Với mỗi bộ kiểm thử, dòng đầu tiên chứa một số nguyên $n$ ($1 \le n \le 10^6$), biểu thị độ dài của dãy.

Dòng tiếp theo chứa $n$ số nguyên $a_1,a_2,\ldots,a_n$ ($0 \le a_i \le 10^9$).

Đảm bảo rằng tổng $n$ trên tất cả các bộ kiểm thử không vượt quá $10^6$.

Dữ liệu ra

Với mỗi bộ kiểm thử, in ra một dòng gồm hai số nguyên. Số đầu tiên biểu thị giá trị lớn nhất của $a_n$, và số thứ hai biểu thị số thao tác ít nhất cần thực hiện.

Ví dụ

Dữ liệu vào 1

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

Dữ liệu ra 1

114514 0
2 1
3 2
5 3