Problem G
Snack Split

Grace is preparing for a long and difficult hike. She has a large bag of trail mix that weighs $G$ grams. Grace wants to share the snacks with her friends, and she knows that $P$ people will join her. To be prepared, she decides to split the trail mix into exactly $P + 1$ smaller bags, so that each bag has the same integer number of grams.

How many grams of trail mix will each smaller bag contain?

Input

The first line of input contains a single integer $N$ ($1 \leq N \leq 1000$), the number of test cases. Each of the next $N$ lines contains two integers $G$ ($1 \leq G \leq 10^{5}$), the weight of Grace’s trail mix bag, and $P$ ($0 \leq P \leq 100\, 000$), the number of people joining Grace. It is guaranteed that it is possible to split $G$ into $P + 1$ equal bags.

Output

Print $N$ lines, one for each test case. Each line should contain a single integer: the weight of each smaller bag.

4
10 0
10 1
10 4
10 9

10
5
2
1