У Little Cyan Fish есть последовательность неотрицательных целых чисел $a_1,a_2,\ldots,a_n$ длины $n$. Little Cyan Fish может любое количество раз выполнять следующую операцию:

• Выбрать целое число $1 \le i \le n$.
• Заменить $a_i$ на $\operatorname{mex}_{1\le k<i}a_k$.

Здесь для множества неотрицательных целых чисел $S$ обозначение $\operatorname{mex} S$ определяется как наименьшее неотрицательное целое число, не принадлежащее множеству $S$. Например, $\operatorname{mex}\{0,1,2,4,6\}=3$, $\operatorname{mex}\{1,2,3\}=0$, $\operatorname{mex}\varnothing=0$.

Little Cyan Fish хочет сделать значение $a_n$ как можно большим с помощью некоторого количества операций (возможно, 0). Little Cyan Fish просит вас вычислить:

1. Максимально возможное значение $a_n$ после любого количества операций;
2. При выполнении пункта 1 — минимальное количество операций, необходимое для достижения этого максимального значения.

Входные данные

Входные данные содержат несколько наборов тестовых данных. Первая строка содержит одно целое число $T$ ($1 \le T$) — количество наборов данных.

Для каждого набора данных первая строка содержит целое число $n$ ($1 \le n \le 10^6$) — длину последовательности.

Следующая строка содержит $n$ целых чисел $a_1,a_2,\ldots,a_n$ ($0 \le a_i \le 10^9$).

Гарантируется, что сумма $n$ по всем наборам данных не превосходит $10^6$.

Выходные данные

Для каждого набора данных выведите одну строку с двумя целыми числами. Первое число — максимальное значение $a_n$, второе — минимальное необходимое количество операций.

Примеры

Входные данные 1

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

Выходные данные 1

114514 0
2 1
3 2
5 3