لدى 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