Consider the fraction, $a/b$, where $a$ and $b$ are positive integers. If $a < b$ and $GCD(a,b) = 1$, it is called a reduced proper fraction.
If we list the set of a reduced proper fraction for $d \leq 8$, (where $d$ is the denominator) in ascending order of size, we get:
$1/8$, $1/7$, $1/6$, $1/5$, $1/4$, $2/7$, $1/3$, $3/8$, $2/5$ , $3/7$, $1/2$, $4/7$, $3/5$, $5/8$, $2/3$, $5/7$, $3/4$, $4/5$,  $5/6$, $6/7$, $7/8$
It can be seen that $2/5$ is the fraction immediately to the left of $3/7$.
By listing the set of reduced proper fractions for $d \leq N$ in ascending order of value, find the numerator and denominator of the fraction immediately to the left of $a/b$ when $a$ and $b$ are given.

-----Input:-----
- First line of input contains an integer $T$, number of test cases
- Next $T$ lines contain $a$ $b$ $N$ separated by space

-----Output:-----
Print the numerator and denominator separated by a space corresponding to each test case on a new line

-----Constraints-----
- $1 \leq T \leq 50$
- $1 \leq a < b \leq 10^9$
- $GCD(a,b) = 1$
- $b < N \leq 10^{15}$

-----Subtasks-----
- 10 points: $1 \leq N \leq 100$
- 30 points : $1 \leq N \leq 10^6$
- 60 points : $1 \leq N \leq 10^{15}$

-----Sample Input:-----
5
3 7 8
3 5 8
4 5 8
6 7 8
1 5 8

-----Sample Output:-----
2 5
4 7
3 4
5 6
1 6

Difficulty: interview

Starter code:

Solutions:
from sys import stdin
from fractions import Fraction

input = stdin.readline

for _ in range(int(input())):
    a, b, n = list(map(int, input().split()))
    ab = Fraction(a, b)

    p = set()

    for i in range(1, n+1):
        for j in range(n, 0, -1):
            x = Fraction(i, j)

            if x > ab:
                break

            p.add(x)

    x = sorted(p)[-2]

    print(x.numerator, x.denominator)


from fractions import Fraction as F


def farey_seq(x, limit):
    l, r = F(0), F(1)
    while l.denominator + r.denominator <= limit:
        m = F(l.numerator + r.numerator, l.denominator + r.denominator)
        if m < x:
            l = m
        else:
            r = m
            if r == x:
                break

    if l.denominator + r.denominator <= limit:
        k = 1 + (limit - (l.denominator + r.denominator)) // r.denominator
        l = F(l.numerator + k * r.numerator, l.denominator + k * r.denominator)

    return l


# ProjectEuler problem:
# print(farey_seq(F(3, 7), 1000000).numerator)

for _ in range(int(input())):
    a, b, n = map(int, input().split())
    r = farey_seq(F(a, b), n)
    print(r.numerator, r.denominator)

# Python code to demonstrate naive 
# method to compute gcd ( recursion ) 

def gcd(a,b): 
	if(b==0): 
		return a 
	else: 
		return gcd(b,a%b) 

T=int(input())
while T:
    a,b,N=map(int,input().split())
    c=set()
    ls=[]
    for i in range(1,N+1):
        for j in range(1,i):
            k=gcd(i,j)
            if(j/i not in c):
                c.add(j/i)
                ls.append([j/i,j//k,i//k])
    ls.sort()
    for i in range(len(ls)):
        if(ls[i][1]==a and ls[i][2]==b):
            break
    print(ls[i-1][1],ls[i-1][2])
    T-=1

R1_HIGH, R1_LOW, R2_HIGH, R2_LOW = 0, 0, 0, 0

def cross_multiply(a, b, i):
    
    nonlocal R1_HIGH
    nonlocal R1_LOW
    nonlocal R2_HIGH
    nonlocal R2_LOW
    
    if i == 1:
        R1_HIGH = 6*a*b
        R1_LOW = R1_HIGH // 2
    elif i == 2:
        R2_HIGH = 6*a*b
        R2_LOW = R2_HIGH // 2



def isLess(a,b,c,d):
    cross_multiply(a, d, 1)
    cross_multiply(c, b, 2)
    
    if (R1_HIGH < R2_HIGH):
        return True
    
    if (R1_HIGH > R2_HIGH):
        return False
    
    return (R1_LOW < R2_LOW)
    


def negb_frac(a,b,N):
    leftN , leftD = 0, 1
    rightN, rightD = 1, 1
    
    while((leftD + rightD) <= N):
        mediantN = leftN + rightN
        mediantD = leftD + rightD
        
        if isLess(mediantN, mediantD, a, b):
            leftN = mediantN
            leftD = mediantD
        else:
            rightN = mediantN
            rightD = mediantD
            
            if (rightN == a and rightD == b):
                break
    
    if ((leftD + rightD) <= N):
        diff = N - (leftD + rightD)
        repeat = 1 + diff // rightD
        leftN += repeat * rightN
        leftD += repeat * rightD
    
    print(leftN, leftD)
    
def __starting_point():
    T = int(input())
    for _ in range(T):
        a,b,N = list(map(int, input().split()))
        negb_frac(a,b,N)
__starting_point()