A. Banis and Cards
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

There are $$$n$$$ cards numbered from $$$1$$$ to $$$n$$$ on the table, and Banis will choose a number $$$m$$$ and try to find the sum of all cards such that the number of the card$$$ \% m = 0$$$, but he's too lazy that he doesn't want to solve it by himself, and that's why he gives the task to you.

Can you help him solve this problem?

Input

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

The only line of each test case contains two numbers $$$n,m(1 \le m\le n\le 10^9)$$$

Output

For each test case, print the answer.

Example
Input
3
12 2
1 1
1010 10
Output
42
1
51510