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 × 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.

Yêu cầu: Hãy giúp Đăng xác định giá trị trung vị của lưới!

Input

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

• \(T\) dòng tiếp theo mỗi dòng chứa hai số nguyên \(N,M (N,M\) lẻ, \(1≤N,M≤10^9 ).\)

Output

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

Ràng buộc

• Subtask 1: 10% điểm: \(N = 1,1 ≤ M ≤ 10^9\)

• Subtask 2: 30% điểm: \(1 ≤ N,M ≤ 1000\)

• Subtask 3: 30% điểm: \(1 ≤ N ≤ 10^5,1 ≤ M ≤ 10^9\)

• Subtask 4: 30% điểm: \(1 ≤ N,M ≤ 10^9\)

Sample Input

1
3 5

Sample Output

23