Julyed

Time Limit: 2000 ms Memory Limit: 65536 KiB

Problem Description

    Julyed is preparing for her CET-6. She has N words to remember, but there is only M days left. If she can’t remember all these words, she won’t pass CET-6. If she can’t pass CET-6, she will be unhappy. But if she remember too many words in one day, she will be unhappy, too. If she is unhappy, tomriddly will be unhappy. So she will remember as little words as she can in one day. For the happiness of both tomriddly and Julyed, how many words at most will Julyed remember in one day?

Input

 Multiple test cases. The first line is an integer T (T <= 10000), indicating the number of test cases.

Each test case is a line with two integers N, M (1 <= N, M <= 200), indicating the number of words to remember and the number of days left.

Output

 One line per case, an integer indicates the answer.

Sample Input

5
6 3
2 1
1 2
5 2
4 3

Sample Output

2
2
1
3
2

Hint

Source

“浪潮杯”山东省第七届ACM大学生程序设计竞赛