Giải bài trực tuyến

Một đoàn khảo cổ phát hiện được một khu vực cho có chứa rất nhiều hóa thạch của nền văn minh YOLO. Trên bản đồ của vùng đất này, mỗi vị trí phát hiện hóa thạch được xem như là một điểm trên mặt phẳng tọa độ Oxy. Vị trí thứ i có tọa độ là (x_i, y_i). Khu đất mà tất cả các hóa thạch được tìm thấy có hình dạng chữ nhật với hai góc dưới trái và trên phải lần lượt là (1, 1) và (N, N) và đã được rào kín lại. Kì lạ thay không có hai vị trí nào có cùng tọa độ X hoặc Y nên các nhà khảo cổ đặt giả thuyết rằng tồn tại một nghi thức chôn cất đặt biệt của những người ở đây. 

Để tiến hành khảo nghiệm, cần phải cô lập các vị trí phát hiện khảo cổ thành những ô riêng biệt. Điều này có thể được thực hiện bằng việc dựng các hàng rào song song với trục X và Y trên hệ trục tọa độ của bản đồ. Theo thiết kế, các hàng rào sẽ được xây sao cho chúng sẽ đi dọc suốt chiều dài hoặc chiều rộng của khu đất tìm thấy hóa thạch nhưng không được đi qua vị trí phát hiện hóa thạch nào để tránh gây hư hại cho chúng. Nhìn trên bản đồ, các hàng rào sẽ chia mặt phẳng ra thành các vùng riêng biệt. Nhằm mục đích thuận tiện cho việc quản lý phân loại các hóa thạch tìm thấy, mỗi vùng chỉ nên chứa tối đa một vị trí phát hiện hóa thạch mà thôi. 

Kinh phí cho việc mua sắm thiết bị đã chiếm phần lớn nguồn đầu tư cho dự án khảo cổ này. Vì thế nên các nhà khảo cổ đang đau đầu lên phương án xây dựng các hàng rào sao cho số lượng của chúng là ít nhất có thể. Các bạn hãy giúp họ nhé!

Input

• Dòng đầu tiên chứa số T là số test. Tiếp theo là T test với định dạng như sau:
  • Dòng 1: Gồm số nguyên dương N duy nhất
  • N dòng tiếp theo, mỗi dòng chứa 2 số nguyên x_i, y_i.

Output

Với mỗi test, ghi ra 1 số duy nhất là số hàng rào cần dựng.

Chấm điểm

• Trong thời gian thi, bài của bạn sẽ được chấm với một test duy nhất là test đề bài.

Giới hạn

Trong tất cả các test:

• 1 ≤ T ≤ 4
• 1 ≤ N ≤ 25
• 1 ≤ x_i, y_i ≤ N

Trong 40% số test đầu tiên, 1 ≤ N ≤ 10, trong 40% test tiếp theo, 1 ≤ N ≤ 20.

Ví dụ

Input:

1
4
1 4
2 1
3 2
4 3

Output:
2

Hình minh họa