ีสวนดอกไม้สวนหนึ่งเป็นตารางสี่เหลี่ยมขนาด 10⁶ แถว x 10⁶ คอลัมน์ มีดอกไม้อยู่ในสวนทั้งหมด N ดอก โดยดอกไม้ดอกที่ i อยู่ที่แถว ri คอลัมน์ ci คุณได้รับมอบหมายให้จัดวางเครื่องฉีดน้ า โดยสามารถจัดวางลงบนแปลงว่าง(แปลงที่ไม่มีดอกไม้) แปลงไหนก็ได้โดยเครื่องฉีดน้ ารุ่นนี้สามารถฉีดน้ าออกเป็นสี่สายในทิศ บนขวา ล่าง และซ้าย ในแนวขนานกับตาราง</p>

นอกจากนี้ ดอกไม้ในสวนมีลักษณะพิเศษคือ เมื่อได้รับน้ าจากทิศใดทิศหนึ่งจะสามารถกระจายน้ าไปในทิศทางที่เหลือได้ด้วย (บน ขวา ล่าง และซ้าย) โดยล าน้ าในแนวตั้งและแนวนอนอยู่คนละระดับสามารถข้ามกันได้อยากทราบว่าต้องใช้เครื่องฉีดน้ าจ านวนน้อยที่สุดกี่เครื่องเพื่อรดน้ าดอกไม้ให้ครบทุกดอก

입력 형식

บรรทัดแรกเป็นจ านวนกรณีทดสอบ T ชุด (1 ≤ T ≤ 20) กรณีทดสอบแต่ละชุดประกอบด้วยข้อมูลดังนี้</p>

1. บรรทัดแรก ระบุจ านวนดอกไม้ในสวน N ดอก (1 ≤ N ≤ 100 000)
2. ถัดมา N บรรทัด ระบุแถวและคอลัมน์ของดอกไม้แต่ละดอก r_i และ c_i ตามล าดับ รับประกันว่าไม่มีดอกไม้มากกว่าหนึ่งดอกอยู่บนแปลงเดียวกัน (1 ≤ r_i, ci ≤ 1 000 000)

ส าหรับกรณีทดสอบแต่ละชุด ให้พิมพ์จ านวนเครื่องฉีดน้ าที่น้อยที่สุดที่สามารถรดน้ าดอกไม้ครบทุกดอกได้

예제 입력

2
4
1 2
2 1
2 3
3 2
9
2 1
1 2
2 3
2 5
1 6
2 7
4 3
5 4
4 5

예제 출력

1
2

힌트

ตัวอย่างการวางเครื่องฉีดน้ าที่ใช้จ านวนเครื่องน้อยที่สุด</p>

กรณีทดสอบที่หนึ่ง

กรณีทดสอบที่สอง