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