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?

Format

Input

Multiple test cases. The first line is an integer $T (T \leq 10000)$, indicating the number of test cases.

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

Output

One line per case, an integer indicates the answer.

Samples

5
6 3
2 1
1 2
5 2
4 3

2
2
1
3
2