import sys, random
input = lambda : sys.stdin.readline().rstrip()


write = lambda x: sys.stdout.write(x+"\n"); writef = lambda x: print("{:.12f}".format(x))
debug = lambda x: sys.stderr.write(x+"\n")
YES="Yes"; NO="No"; pans = lambda v: print(YES if v else NO); INF=10**18
LI = lambda : list(map(int, input().split())); II=lambda : int(input())
def debug(_l_):
    for s in _l_.split():
        print(f"{s}={eval(s)}", end=" ")
    print()
def dlist(*l, fill=0):
    if len(l)==1:
        return [fill]*l[0]
    ll = l[1:]
    return [dlist(*ll, fill=fill) for _ in range(l[0])]

def floor_sum_unsighned(n,m,a,b):
    """sum(((a*i+b)//m) for i in range(n))
    n>=0, m>=1
    """
    ans = 0
    if a>=m:
        ans += (n-1)*n*(a//m)//2
        a %= m
    if b>=m:
        ans += n*(b//m)
        b %= m
    y_max = (a*n + b) // m
    x_max = y_max*m - b
    if y_max==0:
        return ans
    ans += (n - (x_max+a-1)//a) * y_max
    ans += floor_sum(y_max, a, m, (a - x_max%a)%a)
    return ans

# assert(0 <= n && n < (1LL << 32));
#     assert(1 <= m && m < (1LL << 32));
#     unsigned long long ans = 0;
#     if (a < 0) {
#         unsigned long long a2 = internal::safe_mod(a, m);
#         ans -= 1ULL * n * (n - 1) / 2 * ((a2 - a) / m);
#         a = a2;
#     }
#     if (b < 0) {
#         unsigned long long b2 = internal::safe_mod(b, m);
#         ans -= 1ULL * n * ((b2 - b) / m);
#         b = b2;
#     }
#     return ans + internal::floor_sum_unsigned(n, m, a, b);
# }

def floor_sum(n,m,a,b):
    assert(0<=n and 1<=m)
    ans = 0
    if a<0:
        a2 = a%m
        ans -= n*(n-1)//2 * ((a2-a)//m)
        a = a2
    if b<0:
        b2 = b%m
        ans -= n * ((b2-b)//m)
        b = b2
    return ans + floor_sum_unsighned(n,m,a,b)

import math
t = II()
for _ in range(t):
    p,q,k = LI()
    g = math.gcd(p,q)
#     print(p,q,g)
    p //= g
    q //= g
    ok = 10**18 + 100
    ng = 0
    while abs(ok-ng)>1:
        mm = (ok+ng)//2
        qq = min(mm//p + 1, q)
#         qq = q
        val = floor_sum(qq, q, -p, mm) + qq
        if val>k:
            ok = mm
        else:
            ng = mm
    ans = ok * g
    print(ans)