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$ 嘅值盡可能大。Little Cyan Fish 想你計算：

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$。

輸出格式

對每組測試數據，輸出一行兩個整數。第一個整數表示 $a_n$ 嘅最大值，第二個整數表示所需嘅最少操作次數。

樣例

輸入格式 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