Cho dãy số \(a\) có \(n\) phần tử lần lượt là \(k,k+1,k+2,...,n+k-1\). Hãy tìm chỉ số \(i\) sao cho \(x=|a_1+a_2+a_3+...+a_i-a_{i+1}-a_{i+2}-...-a_n|\) là bé nhất có thể. Ký hiệu \(|x|\) biểu diễn giá trị tuyệt đối của \(x\).

Input

Dữ liệu nhập từ tệp ARRAY.INP có cấu trúc như sau:

• Dòng đầu tiên chứa số nguyên dương \(t (1 \leq n \leq 10^4)\)
• \(t\) dòng tiếp theo, mỗi dòng chứa hai số nguyên dương \(n,k (1 \leq n,k \leq 10^9)\) lần lượt là số lượng phần tử của dãy số và điểm bắt đầu của dãy số.

Output

Dữ liệu xuất ra tệp ARRAY.OUT theo cấu trúc như sau:
- Với mỗi test case, hãy in ra kết quả |x| tìm được.

Subtask

• Subtask \(1(30\%\) số điểm\()\) có \(t \leq 10,1 \leq n,k \leq 10^6\).
• Subtask \(2(70\%\) số điểm\()\) không có ràng buộc gì thêm.

4
2 2
7 2
5 3
1000000000 1000000000

1
5
1
347369930