The owner of a company wants to make teams for a new project. There are n employees in his company. An employee can choose the team in which he wants to work in. But he faces a problem in making the teams as each of the n employees dislikes k other employees and doesn’t want to work with them. Also, he does not know the exact identity of the people that a particular employee dislikes. He wants to keep the number of teams as less as possible. Help him find the minimum number of teams such that it is always guaranteed that each employee works with the people he likes.
Note: Liking is not mutual. If A dislikes B then it does not imply that B dislikes A.

Input format

The first line contains a single integer t denoting the number of test cases.
The next t lines contains two integers n and k

Constraints
1<=t<=1000
1<=n<=10¹⁸
0<=k<n

Output format

Print a single integer for each test case – the minimum number of teams that must be formed