Trên mặt phẳng với hệ tọa độ Đề-các vuông góc ~Oxy~ cho ~n~ điểm. Các điểm được đánh số từ ~1~ tới ~n~, điểm thứ ~i~ có tọa độ ~(x_i, y_i)~. Ta nói một điểm được phủ bởi một hình vuông nếu điểm đó nằm ở miền trong của hình vuông hoặc nằm trên cạnh hình vuông.

Câu hỏi 1: Tìm hai hình vuông có cạnh song song với trục tọa độ, kích thước ~k \times k~ để phủ hết tất cả ~n~ điểm đã cho.

Câu hỏi 2: Tìm hai hình vuông có cạnh song song với trục tọa độ, kích thước ~k \times k~, không có điểm chung, để phủ hết tất cả ~n~ điểm đã cho.

Yêu cầu: Tìm số ~k~ nhỏ nhất có thể cho hai câu hỏi trên.

Input

• Dòng đầu tiên chứa số nguyên dương ~C \le 100~ là số bộ dữ liệu, và số nguyên ~q \in \{1, 2\}~ là loại câu hỏi.

• ~C~ nhóm dòng tiếp theo, mỗi nhóm dòng mô tả một bộ dữ liệu:

  • Dòng đầu chứa số nguyên dương ~n \le 10^5~.

  • ~n~ dòng tiếp theo, dòng thứ ~i~ chứa hai số nguyên ~x_i, y_i~ ~(-10^9 \le x_i, y_i \le 10^9)~.

Output

Ứng với mỗi bộ dữ liệu vào, ghi ra một số nguyên duy nhất là câu trả lời cho giá trị ~k~ của câu hỏi tương ứng.

Scoring

Sample Input 1

1 1
5
2 2
3 3
2 4
4 5
5 5

Sample Output 1

2

Sample Input 2

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

Sample Output 2

2
4