小青鱼手中有长度为 $n$ 的非负整数序列 $a_1, a_2, \dots, a_n$。小青鱼可以进行任意次以下操作：

• 选择一个整数 $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} \emptyset = 0$。

小青鱼希望通过若干次操作（可能为 $0$ 次）使得 $a_n$ 的值尽可能大。小青鱼希望你计算：

1. 在任意次操作后，$a_n$ 的最大可能值是多少；
2. 在满足第 1 点的前提下，达到该最大值所需的最少操作次数。

输入格式

输入包含多组测试数据。第一行包含一个整数 $T$ ($1 \le T$)，表示测试数据的组数。

对于每组测试数据： 第一行包含一个整数 $n$ ($1 \le n \le 10^6$)，表示序列的长度。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, 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