Bé Đăng có một bảng phi tiêu đặc biệt được biểu diễn dưới dạng lưới kích thước \(n \times m\), trong đó \(n\) và \(m\) đều là số lẻ. Các hàng được đánh số từ 1 đến \(n\), các cột được đánh số từ 1 đến \(m\). Với ô nằm ở hàng thứ \(i\) và cột thứ \(j\), giá trị của ô này được ký hiệu là \(v_{i,j}\), được xác định bằng cách nối hai số \(i\) và \(j\) lại với nhau. Ví dụ: \(v_{12,345}\ = \ 12345\) và \(v_{20,25}\ = \ 2025\). Đăng muốn ném phi tiêu vào đúng trung tâm của bảng. Tuy nhiên, “trung tâm” được xác định không phải theo tọa độ hình học mà là giá trị trung vị (median) của tất cả các ô trong lưới. Hãy giúp Đăng xác định giá trị trung vị của lưới!

Dữ liệu vào:

- Dòng đầu tiên chứa 1 số nguyên duy nhất \(T \leq \ 5\) (số testcase)

- \(T\) dòng tiếp theo mỗi dòng chứa hai số nguyên cách nhau bởi khoảng trắng: \(n\) và \(m\) (cả hai đều là số lẻ).

Kết quả:

- In ra giá trị trung vị của tất cả các ô trong bảng.

Subtasks:

- 10% điểm: \(n = 1,\ 1 \leq m \leq 10^{9}\)

- 30% điểm: \(1 \leq n,m \leq 1000\)

- 30% điểm: \(1 \leq n \leq 100000,\ 1 \leq m \leq 10^{9}\)

- 30% điểm: \(1 \leq \ n,\ m\ \leq \ 10^{9}\)

Ví dụ:

Giải thích: Lưới có giá trị như sau:

11 12 13 14 15

21 22 23 24 25

31 32 33 34 35

Giá trị trung vị là 23 (vì đây là phần tử đứng giữa khi sắp xếp toàn bộ các giá trị theo thứ tự tăng dần).