Little Cyan Fish ha in mano una sequenza di interi non negativi $a_1,a_2,\ldots,a_n$ di lunghezza $n$. Little Cyan Fish può eseguire la seguente operazione un qualsiasi numero di volte:

• Scegliere un intero $1 \le i \le n$.
• Cambiare $a_i$ in $\operatorname{mex}_{1\le k<i}a_k$.

Qui, per un insieme di interi non negativi $S$, la notazione $\operatorname{mex} S$ è definita come il più piccolo intero non negativo che non compare nell'insieme $S$. Ad esempio, $\operatorname{mex}\{0,1,2,4,6\}=3$, $\operatorname{mex}\{1,2,3\}=0$, $\operatorname{mex}\varnothing=0$.

Little Cyan Fish vuole rendere il valore di $a_n$ il più grande possibile attraverso un certo numero di operazioni (eventualmente 0). Little Cyan Fish vuole che tu calcoli:

1. Qual è il massimo valore possibile di $a_n$ dopo un qualsiasi numero di operazioni;
2. Sulla base del soddisfacimento del punto 1, qual è il numero minimo di operazioni necessarie per raggiungere questo valore massimo.

Input

Ci sono più casi di test. La prima riga dell'input contiene un singolo intero $T$ ($1 \le T$), che indica il numero di casi di test.

Per ciascun caso di test, la prima riga dell'input contiene un intero $n$ ($1 \le n \le 10^6$), che rappresenta la lunghezza della sequenza.

La riga successiva contiene $n$ interi $a_1,a_2,\ldots,a_n$ ($0 \le a_i \le 10^9$).

È garantito che la somma di $n$ su tutti i casi di test non superi $10^6$.

Output

Per ciascun caso di test, stampa una singola riga con due interi. Il primo intero rappresenta il valore massimo di $a_n$, e il secondo intero rappresenta il numero minimo di operazioni necessarie.

Examples

Input 1

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

Output 1

114514 0
2 1
3 2
5 3