Problem: 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 ≤ 10^5).

Each testcase is given in one line, which contains three integers n, p, k (2 ≤ n ≤ 10^6, 1 ≤ p ≤ n - 1, 1 ≤ k ≤ 10^6).

Output format
Print the answer of each testcase in one line.

SAMPLE INPUT
3
12 5 3
12 3 2
3 2 2

SAMPLE OUTPUT
3
4
2

Solution (in PYTHON):

Solution:
def hcf(p , q):
    r = 1
    while(r != 0):
        r = p%q

        p = q
        q = r

    return p
        
t = int(raw_input())

for a in range(t):
    temp = raw_input().split(" ")
    n = int(temp[0])
    p = int(temp[1])
    k = int(temp[2])

    if ((n%p) == 0):
        l = n / p
        
        if k <= l :
            print 1 + p*(k - 1)
        else :
            print "-1"

    else:
        h = hcf(n ,p)
        
        if (h == 1):

            l = n
            
            if k <= l :
                print k
            else :
                print "-1"

        else :

            l = n / h

            if k <= l :
                print 1 + h*(k - 1)
            else :
                print "-1"