Omar is a young programmer, he is aspiring to be one of the most famous programmers like his father who was a World Finals contestant. Omar started his hard training, no more time to waste. Omar imagined an infinite table with rows and columns numbered using the natural numbers. The following figure shows a procedure to traverse such a table assigning a consecutive natural number to each table cell:

A pair of natural numbers (i, j) is represented by the number corresponding to the cell in row i and column j. For instance, the pair (3, 1) is represented by the natural number 11; this fact is noted by P(3, 1) = 11. Omar is trying to write a program which computes P(i, j), but he is still young and needs your help.

Input

In the first line integer n - the number of test cases (n <= 1000). Then n test cases follow. Each test case contains a pair of numbers (0 <= i, j <= 1,000,000,000).

Output

For each test case print P(i, j).

Example

Input:
2
3 1
1000000000 1000000000

Output:
11
2000000002000000000

The young programmer is Omar Ahmed Aly.