King Tle4Ever just appointed Moron as the new Engineer for his country Time Limit Exceeded. In the country of Time Limit Exceeded there are n cities and there is a direct road between each pair of cities. Now cleaning up these roads costs Tle4Ever a lot of money so he wants to demolish some of the roads but not all for sure. He wants to demolish these roads in such a way that if he picks any subset of size q of these cities, than in this subset there should exist at least one pair of cities that doesn't have a direct road between them. 
He asks Moron to come up with a demolishing plan satisfying his conditions. Now, as Moron is not good at coming up with plans, he asks you to help him. Now as coming up with such a plan is really difficult, given n and q you have to tell minimum number of roads that you have to demolish to satisfy King's condition.
For example : Suppose there are 4 cities. Total number of roads in the country are 6. Suppose king chooses q as 3. Than you have to demolish at least 2 roads to satisfy King's condition. If you demolish only 1 road than there will be at least one subset of size 3 which will have road between all pair of cities. Of course you can demolish more than 2 roads but the minimum number of roads that you have to demolish are 2.
[Input]
First line of input contains a single integer t denoting number of test cases.
Next t lines contains 2 integers n and q each.

[Output]
For each test case output the minimum number of roads that you have to demolish.
[Constraints]
1 ≤ t ≤ 10^5
3 ≤ n ≤ 10^6
3 ≤ q ≤ n

SAMPLE INPUT
2
4 3
5 3

SAMPLE OUTPUT
2
4

Explanation

For case 1 : Explanation as in question.
'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
for _ in range(input()):
    n,q = map(int,raw_input().split())
    q=q-1
    ans = n*n - (n%q)*((n+q-1)/q)*((n+q-1)/q) - (q - n%q)*(n/q)*(n/q)
    ans/=2
    ans1 =(n*(n-1))/2 -ans
    print abs(ans1)