Little Cyan Fish は、長さ $n$ の非負整数列 $a_1,a_2,\ldots,a_n$ を持っています。Little Cyan Fish は次の操作を任意の回数行うことができます。

• 整数 $1 \le i \le n$ を選びます。
• $a_i$ を $\operatorname{mex}_{1\le k<i}a_k$ に変更します。

ここで、非負整数の集合 $S$ に対し、$\operatorname{mex} S$ は集合 $S$ に含まれない最小の非負整数と定義されます。例えば、$\operatorname{mex}\{0,1,2,4,6\}=3$、$\operatorname{mex}\{1,2,3\}=0$、$\operatorname{mex}\varnothing=0$ です。

Little Cyan Fish は、何回かの操作（0 回でもよい）によって $a_n$ の値をできるだけ大きくしたいと考えています。次の値を計算してください。

1. 任意の回数の操作後に $a_n$ が取り得る最大値。
2. 1 を満たすことを前提として、その最大値を達成するために必要な操作回数の最小値。

入力

複数のテストケースがあります。入力の最初の行には、テストケース数を表す整数 $T$（$1 \le T$）が与えられます。

各テストケースの最初の行には、数列の長さを表す整数 $n$（$1 \le n \le 10^6$）が与えられます。

次の行には $n$ 個の整数 $a_1,a_2,\ldots,a_n$（$0 \le a_i \le 10^9$）が与えられます。

すべてのテストケースにわたる $n$ の総和は $10^6$ 以下であることが保証されます。

出力

各テストケースについて、2 つの整数を 1 行に出力してください。最初の整数は $a_n$ の最大値、2 番目の整数は必要な操作回数の最小値を表します。

入出力例

入力 1

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

出力 1

114514 0
2 1
3 2
5 3