Cho hàm số \(F(x,\ y):\ \mathbb{N}\times\mathbb{N}\mapsto\mathbb{N}\) thỏa mãn:

• \(F(1,\ 2)=3\);
• \(F(2,\ 4)=6\);
• \(F(3,\ 8)=11\);
• \(F(x,\ y)=F(y,\ x),\ \forall x,\ y\in \mathbb{N}\).

Nhập vào hai số nguyên \(x,\ y\), tính và in ra giá trị của \(F(x,\ y)\).

Input

• Dòng đầu chứa số nguyên dương \(T\): số test cases;
• \(T\) dòng tiếp theo mỗi dòng chứa hai số \(x,\ y\).

Output

• Gồm \(T\) dòng, mỗi dòng là kết quả cho một test case tương ứng.

Ví dụ

Sample input

1
4 1

Sample output

5

Ràng buộc

• \(T\leq10^5\);
• Với mọi bộ test case: \(x,\ y\leq10^9\).