Phép chia lấy dư điều độ

Cho hai số nguyên chẵn $x$ và $y$. Hãy tìm một số nguyên $n$ thỏa mãn

$$1\le n\le 2·{10}^{18}\text{và}nmodx=ymodn,$$

trong đó $amodb$ là số dư của phép chia $a$ cho $b$.

Có thể chứng minh rằng với mọi ràng buộc của đề bài luôn tồn tại ít nhất một số $n$ như vậy. Nếu có nhiều số $n$ thỏa mãn, in ra số nào cũng được.

Dữ liệu vào

• Dòng đầu chứa số nguyên $t$ là số lượng bộ dữ liệu.
• Mỗi dòng trong $t$ dòng tiếp theo chứa hai số nguyên $x$ và $y$ mô tả một bộ dữ liệu.

Dữ liệu ra

Với mỗi bộ dữ liệu, in ra trên một dòng riêng một số nguyên $n$ thỏa mãn điều kiện trên.

Ràng buộc

• $1\le t\le {10}^5$
• $2\le x,y\le {10}^9$
• $x$ và $y$ đều là số chẵn

Ví dụ