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