Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
 User ID: Password:
Register
Language:
The Bad Number
 Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 329 Accepted: 131

Description

John and Brus believe that number N is a very bad number. Thus they try to avoid it every time and everywhere.
Now the guys would like to represent number M as a sum of positive numbers, each of which not exceeding K. But don’t forget about the bad number N! Each summand must not be divisible by N, moreover the number of summands also must not be divisible by N.
Your task is to find the minimal possible number of summands in such representation of M.
For example, if N=3, M=11, K=6 then we can represent M as 5+6, but as far as 6 is divisible by 3 we must have at least 3 summands. But as far as N=3 we can’t have 3 summands and thus the answer is 4. One of the possible ways to represent M is 11=4+4+2+1.

Input

The first line contains single integer T – the number of test cases. Each test case consists of a single line containing three integers N, M and K separated by single spaces.

Output

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 to do this output “-1” (quotes for clarity) instead.

Sample Input

```2
3 11 6
2 12 47
```

Sample Output

```4
-1```

Hint

Constraints:
1 ≤ T ≤ 74,
1 ≤ N, M, K ≤ 1000000000 (109).

Source

[Submit]   [Go Back]   [Status]   [Discuss]

All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator