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: UNKNOWN_DIFFICULTY

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
for _ in range(int(input())):
	(a, b, n) = map(int, input().split())
	r = farey_seq(F(a, b), n)
	print(r.numerator, r.denominator)


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()