Heating

Several days ago you bought a new house and now you are planning to start a renovation. Since winters in your region can be very cold you need to decide how to heat rooms in your house.

Your house has n rooms. In the i-th room you can install at most c_i heating radiators. Each radiator can have several sections, but the cost of the radiator with k sections is equal to k^2 burles.

Since rooms can have different sizes, you calculated that you need at least sum_i sections in total in the i-th room.

For each room calculate the minimum cost to install at most c_i radiators with total number of sections not less than sum_i.

Input

The first line contains single integer n (1 ≤ n ≤ 1000) — the number of rooms.

Each of the next n lines contains the description of some room. The i-th line contains two integers c_i and sum_i (1 ≤ c_i, sum_i ≤ 10^4) — the maximum number of radiators and the minimum total number of sections in the i-th room, respectively.

Output

For each room print one integer — the minimum possible cost to install at most c_i radiators with total number of sections not less than sum_i.

Example

Input

4 1 10000 10000 1 2 6 4 6

Output

100000000 1 18 10

Note

In the first room, you can install only one radiator, so it's optimal to use the radiator with sum_1 sections. The cost of the radiator is equal to (10^4)^2 = 10^8.

In the second room, you can install up to 10^4 radiators, but since you need only one section in total, it's optimal to buy one radiator with one section.

In the third room, there 7 variants to install radiators: [6, 0], [5, 1], [4, 2], [3, 3], [2, 4], [1, 5], [0, 6]. The optimal variant is [3, 3] and it costs 3^2+ 3^2 = 18.

inputFormat

Input

The first line contains single integer n (1 ≤ n ≤ 1000) — the number of rooms.

Each of the next n lines contains the description of some room. The i-th line contains two integers c_i and sum_i (1 ≤ c_i, sum_i ≤ 10^4) — the maximum number of radiators and the minimum total number of sections in the i-th room, respectively.

outputFormat

Output

For each room print one integer — the minimum possible cost to install at most c_i radiators with total number of sections not less than sum_i.

Example

Input

4 1 10000 10000 1 2 6 4 6

Output

100000000 1 18 10

Note

In the first room, you can install only one radiator, so it's optimal to use the radiator with sum_1 sections. The cost of the radiator is equal to (10^4)^2 = 10^8.

In the second room, you can install up to 10^4 radiators, but since you need only one section in total, it's optimal to buy one radiator with one section.

In the third room, there 7 variants to install radiators: [6, 0], [5, 1], [4, 2], [3, 3], [2, 4], [1, 5], [0, 6]. The optimal variant is [3, 3] and it costs 3^2+ 3^2 = 18.

样例

4
1 10000
10000 1
2 6
4 6

100000000
1
18
10

</p>