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