A shopkeeper sells 1 chocolate at Rs. A each. You can exchange B wrappers for 1 chocolate. If you have N Rs, how many maximum chocolates can you get?

Input

The first line consists of an integer t, the number of test cases. Then for the next t lines, each test case consists of 3 integers A, B and N as defined above.

Output

For each test case find the maximum number of chocolates that you can get.

Constraints

1 ≤ t ≤ 1000

1 ≤ A ≤ 20

2 ≤ B ≤ 11

0 ≤ N ≤ 1000000

Example

Input:
5
1 2 0
1 2 5
7 10 7
2 11 4
1 10 4

Output:
0
9
1
2
4