The Bad Number#377
John and Brus believe that the number is a very bad number. Therefore, they try to avoid it at all times and everywhere.
Now the guys want to represent the number as a sum of positive numbers, each not exceeding . However, do not forget about the bad number ! Each summand must not be divisible by , and the number of summands must also not be divisible by .
Your task is to find the minimal possible number of summands in such a representation of .
For example, if N=3, M=11, K=6, then we can represent as 5+6, but is divisible by , so we must have at least summands. But since N=3, we cannot have summands, and thus the answer is . One possible way to represent is 11=4+4+2+1.
The first line contains a single integer — the number of test cases. Each test case consists of a single line containing three integers , , and separated by single spaces.
For each test case, print a single line containing the minimal possible number of summands according to the requirements described above. If it is impossible, output -1 (without quotes).
Constraints
1 \le T \le 74 1 \le N, M, K \le 1000000000~(10^9)
Example 1