Immense Input#12929

Immense Input

Once Charles McGill prepared a problem for SEERC. It's input section looked like this:

The first line contains a single integer (1 \le t \le T)  — the number of test cases.

The first line of each test case contains a single positive integer .

It is guaranteed that the sum of n^2 over all test cases does not exceed .

Chuck realized that he forgot to tell anything about the sum of . What if it's too large and it might take too long to read the input?

Unfortunately, Chuck suffers from electromagnetic hypersensitivity, so he can't use his computer to check this. Help him: find the largest possible sum of under the constraints from the statement.

Input

The first line contains a single integer (1 \le t \le 10^5)  — the number of test cases. The description of test cases follows.

The only line of each test case contains two integers (1 \leq T \leq 10^6, 1 \leq K \leq 10^{18}).

Output

For each test case, output a single integer  — the largest possible sum of under the constraints of the problem.

Examples

Example

Loading
Loading

Note

In the first test case, the largest possible sum is . One way to get it is when t = 4 and corresponding values of are 1, 2, 3, 4: 1^2 + 2^2 + 3^2 + 4^2 = 30, 1 + 2 + 3 + 4 = 10. Another way to get it is with the following values of : 2, 2, 3, 3: 2^2 + 2^2 + 3^2 + 3^2 = 26 < 30, 2 + 2 + 3 + 3 = 10.