chintu-and-candies

Chintu loves to eat candies. He went to a nearby shop to buy n candies.Each candy costs Re 1. But there he finds that he is short by Rs x. So he asked his friend Mintu to lend him some money. Mintu has got Rs n. Mintu being a Math geek agrees to lend him money only on a condition if there are k integers below x that are relatively prime to x. Since Chintu desperately wants to have to those candies so he decides not to tell Mintu the correct amount x but some other amount y(y ≤ n). Chintu being not good in Maths asks for your help in finding that value y.

Input:
First line contains number of test cases T, next T lines contains three numbers n, x and k. n denotes number of candies Chintu wants to buy, x denotes amount by which Chintu is short of and k denotes the number of integers less than x that are relatively prime to x.

Output:
For each test case, print the maximum amount y which Chintu tells Mintu such that there are k integers below y that are relatively prime to y and also Chintu is able to buy desired amount of candies. If no value satisfies the condition then print -1.

Constraints:
1 ≤ T ≤1000

10< n ≤10000

1 ≤ x,k ≤n

SAMPLE INPUT
3
20 10 5
40 12 8
35 5 21

SAMPLE OUTPUT
-1
30
-1

Explanation

Case 2: Chintu needs Rs 12 more so that he can have 40 candies. The number 30 is the only number less than 40 which has 8 numbers (1,7,11,13,17,19,23 and 29) less than itself which are co-prime to it. Also if he asks for Rs 30 then he will be able to buy the required number of candies.

Case 1: There is no number less than 20 and greater than 10 such that there are 5 numbers less than it which are co-prime to it.

Source: hackerearth | Difficulty: MEDIUM


Solutions: