Farabi loves mathematics very much. He wants to play with numbers, specially with even and odd numbers.

One day he gets a line and an idea came to his mind.

He wants to assign the numbers in the line in the non-decreasing order but in different manner.

He wants to assign:

1. The even numbers in the odd indices and odd numbers in the even indices.
2. All the even numbers must be in the non-decreasing order and also all the odd numbers must be in non decreasing order, means the even numbers will not change their relative position and vice versa.

As example: substituting value (2 and 4) in index (1 and 3) respectively, and value (1 and 3) in index (2 and 4) respectively. The sequence will look like the following,

    2, 1, 4, 3, 6 ...

After doing this he shows that to his teacher Mr. Jhon But instead of appreciating him Mr. Jhon gave him another task:

"The task is to find the summation between two indices (a and b)".

After trying this more than a day Farabi become frustrated and He wants your help to solve this problem.

can you help him?

Input

In the first line there will be an integer T (1 <= T <= 10) the number of test cases.

In each test case there will be two integer a and b.

1 <= a, b <= 10^9

Output

For each test case print the output in one line.

Example

Input:
2
1 4
1 1000000000

Output:
10
500000000500000000