Little Cyan Fish has a non-negative integer sequence $a_1,a_2,\ldots,a_n$ of length $n$ in his hand. Little Cyan Fish can perform the following operation any number of times:

• Choose an integer $1 \le i \le n$.
• Change $a_i$ to $\operatorname{mex}_{1\le k<i}a_k$.

Here, for a set of non-negative integers $S$, the notation $\operatorname{mex} S$ is defined as the smallest non-negative integer that does not appear in the set $S$. For example, $\operatorname{mex}\{0,1,2,4,6\}=3$, $\operatorname{mex}\{1,2,3\}=0$, $\operatorname{mex}\varnothing=0$.

Little Cyan Fish wants to make the value of $a_n$ as large as possible through some number of operations (possibly 0). Little Cyan Fish wants you to calculate:

1. What is the maximum possible value of $a_n$ after any number of operations;
2. On the basis of satisfying 1, what is the minimum number of operations required to achieve this maximum value.

Input

There are multiple test cases. The first line of the input contains a single integer $T$ ($1 \le T$), indicating the number of test cases.

For each test case, the first line of the input contains an integer $n$ ($1 \le n \le 10^6$), representing the length of the sequence.

The next line contains $n$ integers $a_1,a_2,\ldots,a_n$ ($0 \le a_i \le 10^9$).

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^6$.

Output

For each test case, output a single line with two integers. The first integer represents the maximum value of $a_n$, and the second integer represents the minimum number of operations required.

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