Little Cyan Fish tem uma sequência de inteiros não negativos $a_1,a_2,\ldots,a_n$ de comprimento $n$. Little Cyan Fish pode realizar a seguinte operação um número arbitrário de vezes:

• Escolher um inteiro $1 \le i \le n$.
• Alterar $a_i$ para $\operatorname{mex}_{1\le k<i}a_k$.

Para um conjunto de inteiros não negativos $S$, a notação $\operatorname{mex} S$ é definida como o menor inteiro não negativo que não pertence ao conjunto $S$. Por exemplo, $\operatorname{mex}\{0,1,2,4,6\}=3$, $\operatorname{mex}\{1,2,3\}=0$, $\operatorname{mex}\varnothing=0$.

Little Cyan Fish quer tornar o valor de $a_n$ tão grande quanto possível através de um certo número de operações (possivelmente 0). Little Cyan Fish quer que calcules:

1. O maior valor possível de $a_n$ após um número arbitrário de operações;
2. Satisfazendo o ponto 1, o menor número de operações necessário para atingir esse valor máximo.

Entrada

Existem vários casos de teste. A primeira linha da entrada contém um único inteiro $T$ ($1 \le T$), que indica o número de casos de teste.

Para cada caso de teste, a primeira linha contém um inteiro $n$ ($1 \le n \le 10^6$), que representa o comprimento da sequência.

A linha seguinte contém $n$ inteiros $a_1,a_2,\ldots,a_n$ ($0 \le a_i \le 10^9$).

É garantido que a soma de $n$ em todos os casos de teste não excede $10^6$.

Saída

Para cada caso de teste, imprime uma linha com dois inteiros. O primeiro representa o valor máximo de $a_n$ e o segundo representa o menor número de operações necessário.

Exemplos

Entrada 1

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

Saída 1

114514 0
2 1
3 2
5 3