Xoắn ốc số

Nguồn CSES Problem Set

Đề bài

Một xoắn ốc số là một lưới vô hạn gồm các số nguyên dương, trong đó ô ở góc trên bên trái chứa số $1$.

Năm lớp đầu tiên của xoắn ốc có dạng:

 1   2   9  10  25
 4   3   8  11  24
 5   6   7  12  23
16  15  14  13  22
17  18  19  20  21

Các hàng được đánh số từ trên xuống dưới và các cột được đánh số từ trái sang phải, bắt đầu từ $1$.

Nhiệm vụ của bạn là xác định số nằm tại hàng $y$ và cột $x$ của xoắn ốc.

Input

Dòng đầu tiên chứa số nguyên $t$ — số lượng truy vấn.

Tiếp theo là $t$ dòng, mỗi dòng chứa hai số nguyên $y$ và $x$ — lần lượt là chỉ số hàng và chỉ số cột cần xác định.

Output

Với mỗi truy vấn, in ra trên một dòng số nằm tại hàng $y$ và cột $x$ của xoắn ốc.

Subtask

• Subtask 1 — 20%: $1 \le t \le 100$; $1 \le y,x \le 100$.
• Subtask 2 — 30%: $1 \le t \le 100$; $1 \le y,x \le 10^5$.
• Subtask 3 — 50%: $1 \le t \le 10^5$; $1 \le y,x \le 10^9$.

Ví dụ

Input

3
2 3
1 1
4 2

Output

8
1
15

Giải thích

Xét từng truy vấn trong ví dụ:

• Với $y=2$ và $x=3$, ta cần tìm ô ở hàng thứ $2$, cột thứ $3$. Quan sát xoắn ốc, hàng thứ $2$ bắt đầu bằng các giá trị $4,3,8,\ldots$, vì vậy ô này chứa số $8$.

• Với $y=1$ và $x=1$, đây chính là ô ở góc trên bên trái của xoắn ốc. Theo định nghĩa, ô này chứa số $1$.

• Với $y=4$ và $x=2$, hàng thứ $4$ bắt đầu bằng các giá trị $16,15,14,13,\ldots$, vì vậy ô ở cột thứ $2$ chứa số $15$.

Do đó ba kết quả lần lượt là:

8
1
15