Little Cyan Fish tiene una secuencia de enteros no negativos $a_1,a_2,\ldots,a_n$ de longitud $n$. Little Cyan Fish puede realizar la siguiente operación cualquier número de veces:

• Elegir un entero $1 \le i \le n$.
• Cambiar $a_i$ por $\operatorname{mex}_{1\le k<i}a_k$.

Para un conjunto de enteros no negativos $S$, la notación $\operatorname{mex} S$ se define como el menor entero no negativo que no aparece en el conjunto $S$. Por ejemplo, $\operatorname{mex}\{0,1,2,4,6\}=3$, $\operatorname{mex}\{1,2,3\}=0$, $\operatorname{mex}\varnothing=0$.

Little Cyan Fish quiere que el valor de $a_n$ sea lo más grande posible mediante cierto número de operaciones (posiblemente 0). Little Cyan Fish quiere que calcules:

1. El máximo valor posible de $a_n$ después de cualquier número de operaciones;
2. Sujeto a satisfacer el punto 1, el mínimo número de operaciones necesario para alcanzar ese valor máximo.

Entrada

Hay varios casos de prueba. La primera línea de la entrada contiene un único entero $T$ ($1 \le T$), que indica el número de casos de prueba.

Para cada caso de prueba, la primera línea contiene un entero $n$ ($1 \le n \le 10^6$), que representa la longitud de la secuencia.

La siguiente línea contiene $n$ enteros $a_1,a_2,\ldots,a_n$ ($0 \le a_i \le 10^9$).

Se garantiza que la suma de $n$ sobre todos los casos de prueba no supera $10^6$.

Salida

Para cada caso de prueba, imprime una línea con dos enteros. El primero representa el máximo valor de $a_n$ y el segundo representa el mínimo número de operaciones necesario.

Ejemplos

Entrada 1

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

Salida 1

114514 0
2 1
3 2
5 3