L. Stuck on Bricks
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Meruem the ant is on an infinite brick wall, where every brick is a $$$1$$$ by $$$2$$$ inch rectangle, and each row is a duplicate of the previous row, shifted $$$1$$$ inch to the right. Every day he starts on the lower left point of a brick and travels in a straight line to the point $$$x$$$ inches to the east and $$$y$$$ inches to the north. How many bricks does Meruem pass through?

Input

The input consists of multiple test cases. The first line contains a single integer $$$t$$$ $$$(1 \le t \le 100)$$$ $$$-$$$ the number of test cases. The description of the test cases follows.

Each test case consists of one line containing two integers $$$x$$$ and $$$y$$$ $$$(1 \le x, y \le 10^{10})$$$.

It is guaranteed that $$$x \cdot y \le 10^{10}$$$.

The first five test cases (not including the sample) satisfy $$$x, y \le 1000$$$.

Output

For each test case, print one integer — the number of bricks Meruem passes through.

Example
Input
3
3 3
5 2
5 1
Output
3
4
3
Note

Travelling to $$$(3,3)$$$ goes through three bricks.

Travelling to $$$(5,2)$$$ goes through four bricks.

Travelling to $$$(5,1)$$$ goes through three bricks

Idea: thehunterjames

Preparation: thehunterjames, Esomer

Occurrences: Novice, problem 8