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

```python

USER_FILENAME = "<user_code>"
import sys, json, builtins
import math, heapq, bisect, itertools, functools, collections, statistics, fractions, decimal, operator, array, random, re, string, os, pathlib
try:
    import resource as _res
except Exception:
    _res = None
from collections import Counter, defaultdict, deque, OrderedDict
from functools import lru_cache, reduce
from itertools import accumulate, permutations, combinations, product
from math import gcd, ceil, floor, sqrt
from decimal import Decimal
try:
    from typing import *
except Exception:
    pass
try:
    sys.setrecursionlimit(1_000_000)
except Exception:
    pass
try:
    import site as _site
    try:
        _sys_sites = _site.getsitepackages() if hasattr(_site, "getsitepackages") else []
        for _p in _sys_sites:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
    try:
        _usp = _site.getusersitepackages()
        if isinstance(_usp, str):
            _usp = [_usp]
        for _p in _usp:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
except Exception:
    pass

ns = {"__name__": "__main__"}
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = 'R1_HIGH, R1_LOW, R2_HIGH, R2_LOW = 0, 0, 0, 0\n\ndef cross_multiply(a, b, i):\n    \n    nonlocal R1_HIGH\n    nonlocal R1_LOW\n    nonlocal R2_HIGH\n    nonlocal R2_LOW\n    \n    if i == 1:\n        R1_HIGH = 6*a*b\n        R1_LOW = R1_HIGH // 2\n    elif i == 2:\n        R2_HIGH = 6*a*b\n        R2_LOW = R2_HIGH // 2\n\n\n\ndef isLess(a,b,c,d):\n    cross_multiply(a, d, 1)\n    cross_multiply(c, b, 2)\n    \n    if (R1_HIGH < R2_HIGH):\n        return True\n    \n    if (R1_HIGH > R2_HIGH):\n        return False\n    \n    return (R1_LOW < R2_LOW)\n    \n\n\ndef negb_frac(a,b,N):\n    leftN , leftD = 0, 1\n    rightN, rightD = 1, 1\n    \n    while((leftD + rightD) <= N):\n        mediantN = leftN + rightN\n        mediantD = leftD + rightD\n        \n        if isLess(mediantN, mediantD, a, b):\n            leftN = mediantN\n            leftD = mediantD\n        else:\n            rightN = mediantN\n            rightD = mediantD\n            \n            if (rightN == a and rightD == b):\n                break\n    \n    if ((leftD + rightD) <= N):\n        diff = N - (leftD + rightD)\n        repeat = 1 + diff // rightD\n        leftN += repeat * rightN\n        leftD += repeat * rightD\n    \n    print(leftN, leftD)\n    \ndef __starting_point():\n    T = int(input())\n    for _ in range(T):\n        a,b,N = list(map(int, input().split()))\n        negb_frac(a,b,N)\n__starting_point()'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: