Time Limit: 2000 MS    Memory Limit: 65536 K 


Description

When fengzlzl was studying in database class, Mr. Zhang gave his students an interesting problem: Here is a matrix A as followed: 1 3 4 10 11 21 22 ... 2 5 9 12 20 ... 6 8 13 19 ... 7 14 18 ... 15 17 ... 16 ... .. . The size of the matrix is infinity. Mr. Zhang's question is, for A[x][y]=c, give you the value of c,can you tell me the value of x and y? Though there are many methods to solve this problem, yet fengzlzl thinks it is still too easy. So he modifies the question: For A[x][y]=c, give you the value of x and y, can you tell me the sum of A[x][1], A[x][2], ... A[x][y]?

Input

The first line of input is an intger T( 1 <= T <= 2000 ), which means the total number of test case. Every line of the following lines is for one test case. For each test case, just one line, contains the two integers x and y. ( 1 <= x,y <= 1000000)

Output

For each test case, just one line, output the sum.

Sample Input

3 1 1 1 5 3 3

Sample Output

1 29 27

Source

8th SCUPC

Author

fengzlzl