Little Cyan Fish possède une suite d'entiers non négatifs $a_1,a_2,\ldots,a_n$ de longueur $n$. Little Cyan Fish peut effectuer l'opération suivante un nombre quelconque de fois :

• Choisir un entier $1 \le i \le n$.
• Remplacer $a_i$ par $\operatorname{mex}_{1\le k<i}a_k$.

Ici, pour un ensemble d'entiers non négatifs $S$, la notation $\operatorname{mex} S$ désigne le plus petit entier non négatif qui n'appartient pas à $S$. Par exemple, $\operatorname{mex}\{0,1,2,4,6\}=3$, $\operatorname{mex}\{1,2,3\}=0$, $\operatorname{mex}\varnothing=0$.

Little Cyan Fish souhaite rendre la valeur de $a_n$ aussi grande que possible en effectuant un certain nombre d'opérations (éventuellement 0). Little Cyan Fish vous demande de calculer :

1. La valeur maximale possible de $a_n$ après un nombre quelconque d'opérations ;
2. Sous réserve de satisfaire le point 1, le nombre minimal d'opérations nécessaires pour atteindre cette valeur maximale.

Entrée

Il y a plusieurs cas de test. La première ligne de l'entrée contient un entier $T$ ($1 \le T$), qui indique le nombre de cas de test.

Pour chaque cas de test, la première ligne contient un entier $n$ ($1 \le n \le 10^6$), qui représente la longueur de la suite.

La ligne suivante contient $n$ entiers $a_1,a_2,\ldots,a_n$ ($0 \le a_i \le 10^9$).

Il est garanti que la somme de $n$ sur tous les cas de test ne dépasse pas $10^6$.

Sortie

Pour chaque cas de test, affichez une ligne contenant deux entiers. Le premier représente la valeur maximale de $a_n$, et le second le nombre minimal d'opérations nécessaires.

Exemples

Entrée 1

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

Sortie 1

114514 0
2 1
3 2
5 3