Trisha has a cute little puppy. She plays a game with him everyday, where he goes and gets her coins from around the house, and for every coin he gets her, Trisha gives him a cookie.

One day Trisha’s puppy, finds something interesting. A wooden chest containing N coins! Now he’s so excited that he’ll get a huge reward. But as he is just a little puppy, and he can't open it by himself. The only thing he can really do is bark. He can use his barking to call Trisha’s other pets to seek their help. He can set the loudness of his barking very precisely, and therefore you can assume that he can choose to call any number of pets, from a minimum of 0, to a maximum of K.

When the pets come and open the chest, they divide all the coins between them in such a way that everyone will get the same amount of coins and this amount is maximal possible. If some coins are not used they will leave it on the ground and the puppy will take them after they go away. Since the puppy is clearly not a fool, he understands that his profit depends on the number of pets he will call. Now he has come to you for help, help him find the maximum possible number of coins he can get.

Input Format

The first line of the input contains an integer T denoting the number of test cases. Each of next T lines contains 2 space-separated integers: N and K, for this test case.

Output Format

For each test case output one integer - the maximum possible number of coins the puppy can get.

Constraints

1 ≤ T ≤ 50
1 ≤ N
K ≤ 10^5

Sample Input

2
5 2
11 3

Sample Output

1
2