VegiCat มีช่วงปิดของจำนวนเต็ม $n$ ช่วง ได้แก่ $[l_1, r_1], [l_2, r_2], \ldots, [l_n, r_n]$

เขาต้องการสร้างลำดับ $a_1, a_2, \ldots, a_n$ โดยการเลือกจำนวนเต็ม $a_i$ จากแต่ละช่วง $[l_i, r_i]$ นั่นคือ $l_i \le a_i \le r_i$ สำหรับทุก ๆ $1 \le i \le n$

ตำแหน่ง $i$ จะถูกเรียกว่า ตำแหน่งสถิติใหม่ (record position) ถ้า $a_i > a_j$ สำหรับทุก ๆ $1 \le j < i$ โดยเฉพาะอย่างยิ่ง ตำแหน่ง $1$ จะเป็นตำแหน่งสถิติใหม่เสมอ

จงช่วย VegiCat ทำให้จำนวนตำแหน่งสถิติใหม่มีค่าน้อยที่สุด และแสดงผลจำนวนที่น้อยที่สุดนี้

ข้อมูลนำเข้า

บรรทัดแรกประกอบด้วยจำนวนเต็ม $T$ ($1 \le T \le 10^4$) คือจำนวนกรณีทดสอบ รายละเอียดของแต่ละกรณีทดสอบมีดังต่อไปนี้

บรรทัดแรกของแต่ละกรณีทดสอบประกอบด้วยจำนวนเต็ม $n$ ($1 \le n \le 10^6$) คือจำนวนช่วง

บรรทัดที่ $i$ จาก $n$ บรรทัดถัดไปประกอบด้วยจำนวนเต็มสองจำนวน $l_i, r_i$ ($-10^9 \le l_i \le r_i \le 10^9$) ซึ่งอธิบายช่วงที่สามารถเลือกได้ในตำแหน่ง $i$

รับประกันว่าผลรวมของ $n$ จากทุกกรณีทดสอบจะไม่เกิน $10^6$

ข้อมูลส่งออก

สำหรับแต่ละกรณีทดสอบ ให้แสดงผลจำนวนเต็มหนึ่งจำนวน — จำนวนตำแหน่งสถิติใหม่ที่น้อยที่สุดที่เป็นไปได้

ตัวอย่าง

ข้อมูลนำเข้า 1

2
4
1 1
1 100
20 20
30 30
8
-3 -1
-5 4
0 1
2 2
1 8
5 6
10 12
12 12

ข้อมูลส่งออก 1

2
4

หมายเหตุ

ในกรณีทดสอบแรก ลำดับที่เหมาะสมที่สุดลำดับหนึ่งคือ $a = [1, 100, 20, 30]$ ตำแหน่งสถิติใหม่ของลำดับนี้คือ $1$ และ $2$

ในกรณีทดสอบที่สอง ลำดับที่เหมาะสมที่สุดลำดับหนึ่งคือ $a = [-1, 4, 1, 2, 8, 6, 12, 12]$ ตำแหน่งสถิติใหม่ของลำดับนี้คือ $1, 2, 5$ และ $7$ ตำแหน่ง $8$ ไม่ใช่สถิติใหม่เนื่องจากค่าของมันเท่ากับค่าสูงสุดที่เคยพบมาแล้ว