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⁵
3<=n<=10⁶
3<=q<=n