ל-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