Little Cyan Fish ma ciąg nieujemnych liczb całkowitych $a_1,a_2,\ldots,a_n$ o długości $n$. Little Cyan Fish może dowolną liczbę razy wykonać następującą operację:

• Wybrać liczbę całkowitą $1 \le i \le n$.
• Zmienić $a_i$ na $\operatorname{mex}_{1\le k<i}a_k$.

Dla zbioru nieujemnych liczb całkowitych $S$ zapis $\operatorname{mex} S$ oznacza najmniejszą nieujemną liczbę całkowitą, która nie należy do zbioru $S$. Na przykład $\operatorname{mex}\{0,1,2,4,6\}=3$, $\operatorname{mex}\{1,2,3\}=0$, $\operatorname{mex}\varnothing=0$.

Little Cyan Fish chce, aby po pewnej liczbie operacji (być może 0) wartość $a_n$ była jak największa. Little Cyan Fish prosi cię o obliczenie:

1. Maksymalnej możliwej wartości $a_n$ po dowolnej liczbie operacji;
2. Przy spełnieniu punktu 1 — minimalnej liczby operacji potrzebnych do osiągnięcia tej maksymalnej wartości.

Wejście

Dane zawierają wiele przypadków testowych. Pierwszy wiersz wejścia zawiera jedną liczbę całkowitą $T$ ($1 \le T$), oznaczającą liczbę przypadków testowych.

Dla każdego przypadku testowego pierwszy wiersz zawiera liczbę całkowitą $n$ ($1 \le n \le 10^6$), oznaczającą długość ciągu.

Następny wiersz zawiera $n$ liczb całkowitych $a_1,a_2,\ldots,a_n$ ($0 \le a_i \le 10^9$).

Gwarantuje się, że suma $n$ po wszystkich przypadkach testowych nie przekracza $10^6$.

Wyjście

Dla każdego przypadku testowego wypisz jeden wiersz zawierający dwie liczby całkowite. Pierwsza oznacza maksymalną wartość $a_n$, a druga minimalną wymaganą liczbę operacji.

Przykład

Wejście 1

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

Wyjście 1

114514 0
2 1
3 2
5 3