Vào đêm giao thừa Tết Nam có một chiếc túi thần kì có thể random ra một trong \(n\) loại vớ bất kì. Biết mỗi loại vớ chỉ có tối đa \(m\) cái. Hãy giúp Nam tìm số lần phải lấy vớ để được \(x\) cái cùng loại.

Input

• Số nguyên \(Q\) là số truy vấn \((1 \leq Q \leq 1000)\).
• Số nguyên \(n, m, x\) \((1 \leq n, m, x \leq 10^8)\).

Output

• Kết quả của mỗi truy vấn (nếu không thể lấy được \(x\) cái vớ thì in ra \(-1\)).

Example

10
1 5 3
2 3 2
5 10 1
4 4 4
4 4 5
10 1 1
10 1 2
100 100 50
7 8 8
7 8 9

3
3
1
13
-1
1
-1
4901
50
-1