import sys input = sys.stdin.readline from math import gcd # https://github.com/shakayami/ACL-for-python/blob/master/math.py # \sum_{i=0}^{n-1} (a * i + b)//m def floor_sum(n,m,a,b): ans=0 if a<0: a2=a%m return floor_sum(n,m,a2,b)-n*(n-1)*((a2-a)//m)//2 if b<0: b2=b%m return floor_sum(n,m,a,b2)-n*((b2-b)//m) 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 def BinarySearch(yes, no, P, Q, K): while abs(yes - no) != 1: mid = (yes + no)//2 num = min(P, mid//Q + 1) if floor_sum(num, P, -Q, mid) + num - 1 >= K: yes = mid else: no = mid return yes T = int(input()) for _ in range(T): P, Q, K = map(int, input().split()) g = gcd(P, Q) P //= g Q //= g yes = 10 ** 20 no = -1 print(BinarySearch(yes, no, P, Q, K) * g)