Кішкентай Көгілдір Балықтың қолында ұзындығы $n$ болатын теріс емес бүтін сандар тізбегі $a_1,a_2,\ldots,a_n$ бар. Кішкентай Көгілдір Балық келесі амалды кез келген рет орындай алады:

• $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$.

Кішкентай Көгілдір Балық бірнеше амал (мүмкін 0) арқылы $a_n$ мәнін мүмкіндігінше үлкен еткісі келеді. Кішкентай Көгілдір Балық сізден келесіні есептеуді сұрайды:

1. Кез келген амалдар санынан кейін $a_n$-нің ең үлкен мүмкін мәні қандай;
2. 1-тармақты қанағаттандыру негізінде осы ең үлкен мәнге жету үшін қажетті ең аз амалдар саны қандай.

Input

Бірнеше тест жағдайлары бар. Кірістің бірінші жолында тест жағдайларының санын білдіретін бір бүтін сан $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$-нен аспайтынына кепілдік беріледі.

Output

Әрбір тест жағдайы үшін екі бүтін саннан тұратын бір жолды шығарыңыз. Бірінші бүтін сан $a_n$-нің ең үлкен мәнін, ал екінші бүтін сан қажетті ең аз амалдар санын білдіреді.

Examples

Input 1

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

Output 1

114514 0
2 1
3 2
5 3