A Darie is a special circle. Numbers 1, 2, ..., n are written clockwise around this circle in order. You can stand on a number! Initially Rasta is on number 1. In each step, he jumps exactly p numbers clockwise. For example if n = 3 and he is standing on number 1:
If p = 1 then he jumps to number 2.
Or if p = 2 he jumps to number 3.
He does this until he reaches a number he's been on before (for example, if n = 3, p = 1 he stops after three jumps).
Then he writes down the numbers he had been on, as a sequence s in increasing order.
He's not a Mr.Memmory, so he can't remember this sequence. He asks you to help him by telling him the k-th number in this sequence (or -1 if size of s is less than k).
Input format
The first line of input contains an integer t, the number of testcases (1 ≤ t ≤ 105).
Each testcase is given in one line, which contains three integers n, p, k (2 ≤ n ≤ 106, 1 ≤ p ≤ n - 1, 1 ≤ k ≤ 106).
Output format
Print the answer of each testcase in one line.