You have a wire of length n metres. You would like to cut it into k sections such that the pieces are as long as possible and all the same length (you may trim the ends of the wire as much as you want).

The problem is your wire cutters are very thick and whenever you cut the wire in the middle, you also end up taking out m metres of wire which you then throw away.

Determine the longest length that you can make the k sections of wire. Remember you know that can always at least make k sections of length 0.

Input

Your first line will contain an integer T representing the number of test cases.

For each test case there will be a single line containing three space-separated integers n (n < 10^9), k (k < 10^9) and m (m < 10^9) respectively.

Output

You should output a single integer per test case representing the length of your k cut wires (the longest length possible).

Input 1
3
1 1 1
100 2 20
44 3 5

Output 1
1
40
11