Valentine's Day is coming and our friend Mr.IDC has fallen in love with a girl. He just could not control his feelings and went to propose her.
When he proposed her the girl gave him a challenge and asked him to solve it and the condition was if he will solve the challenge successfully then only she will accept his proposal.
Since the girl likes mathematics very much so she asked him to calculate the sum of numbers from 1 to N as:

for ( i=1;i<=N;i++ )
sum += i % MOD;
( Since the girl is also in love with him so she does not want him to waste his time on large numbers, therefore she is gave him the MOD value also to reduce his calculations. )
Now she wants him to calculate the sum using the above definition. This sum will also prove how much he love her. ;)

Input
First Line of input contains T, the number of testcases.
The next T lines will contain two integers N and MOD.

Output
For each testcase print the output in a new line.

Constraints:

1 <= T <= 1000
1 <= N <= 10^9
1 <= MOD <= 10^9

Example
Input:
3
20 5
10 2
5 3

Output:
40
5
6

Explanation
Testcase 1: For N = 20 m = 5,
Sum = 1%5 + 2%5 + 3%5 + 4%5 + 5%5 + 6%5 + 7%5 + 8%5 + 9%5 + 10%5 + 11%5 + 12%5 + 13%5 + 14%5 + 15%5 + 16%5 + 17%5 + 18%5 + 19%5 + 20%5 = 40
You can check yourself for testcase 2 and 3.

见题面

见题面