Given N and M Dexter wants to know how many pairs a,b(1 ≤ a < b ≤N) are there such that (a+b) is divisible by M.
For example when N=4 and M=3, there are 2 possible pairs the sum of which is divisible by M and they are (1,2) and (2,4).

------ Input ------

First line of input contains T(≤100000) which is the number of test cases. Each of the next T lines contains two integers N(1 ≤ N ≤ 10^{9}) and M(2 ≤ M ≤ 10^{9}).

------ Output ------

Output one line per testcase, the number of pairs (a,b) as described before.

----- Sample Input 1 ------
3
2 3
4 3
1 6
----- Sample Output 1 ------
1
2
0

见题面

见题面