好好看文件名！！！

直接在Stern Brocot树上走，每次走到一个点，通过类欧几里得求出来这个斜率的直线左侧的整点个数。

然后二分在Stern Brocot树上向左或者向右跳。

复杂度$O(Tlog^3n)$

$$ \text{求}\frac{x}{y}<\frac{a}{b},x\in \left[ \text{1,}n \right] \cap \text{Z,}y\in \left[ \text{1,}m \right] \cap \text{Z的}\frac{x}{y}\text{个数。} \\ \text{式子变形得到} \\ x<\frac{ay}{b} \\ xb<ay \\ \text{考虑直接枚举}x,\text{则可得}\sum_{1\le x\le n}{\sum_{1\le y\le m}{\left[ y>\frac{bx}{a} \right]}} \\ =\sum_{1\le x\le n}{\sum_{1\le y\le m}{\left[ y>\lfloor \frac{bx}{a} \rfloor \right]}} \\ =\sum_{1\le x\le n}{\left( m-\lfloor \frac{bx}{a} \rfloor \right) \left[ m>\lfloor \frac{bx}{a} \rfloor \right]} \\ \text{由}m>\lfloor \frac{bx}{a} \rfloor \text{可得}m>\frac{bx}{a}\text{，进而}ma>bx \\ \text{可得}x<\frac{ma}{b},\text{即}x<\lceil \frac{ma}{b} \rceil ,\text{即}x\le \lceil \frac{ma}{b} \rceil -1 \\ \text{故原式等价于}\sum_{1\le x\le \min \left( n,\lceil \frac{ma}{b} \rceil -1 \right)}{m-\lfloor \frac{bx}{a} \rfloor} \\ =m\times \min \left( n,\lceil \frac{ma}{b} \rceil -1 \right) -\sum_{1\le x\le \min \left( n,\lceil \frac{ma}{b} \rceil -1 \right)}{\lfloor \frac{bx}{a} \rfloor} \\ \text{考虑如何计算}f\left( n,a,b,c \right) =\sum_{0\le i\le n}{\lfloor \frac{ai+b}{c} \rfloor} \\ f\left( n,a,b,c \right) =\sum_{0\le i\le n}{\sum_{0\le j\le \lfloor \frac{ai+b}{c} \rfloor -1}{1}} \\ =\sum_{0\le i\le n}{\sum_{0\le j\le \lfloor \frac{an+b}{c} \rfloor -1}{\left[ j<\lfloor \frac{ai+b}{c} \rfloor \right]}} \\ =\sum_{0\le j\le \lfloor \frac{an+b}{c} \rfloor -1}{\sum_{0\le i\le n}{\left[ j<\lfloor \frac{ai+b}{c} \rfloor \right]}} \\ \text{由于}\lfloor \frac{ai+b}{c} \rfloor =\lceil \frac{ai+b-c+1}{c} \rceil \\ \left( \begin{array}{c} \text{证明直接考虑:对于}\frac{an+b}{c}\text{为非整数时,}\\ \lfloor \frac{an+b}{c} \rfloor =\lceil \frac{an+b}{c}-1 \rceil =\lceil \frac{an+b-c}{c} \rceil \text{成立,对于整数，加上修正值}\frac{1}{c}\text{即可}\\ \end{array} \right) \\ \text{原式}=\sum_{0\le j\le \lfloor \frac{an+b}{c} \rfloor -1}{\sum_{0\le i\le n}{\left[ j<\lceil \frac{ai+b-c+1}{c} \rceil \right]}} \\ \text{又因为当}a<\lceil \frac{b}{c} \rceil \text{时，有}ac<b \\ \text{原式}=\sum_{0\le j\le \lfloor \frac{an+b}{c} \rfloor -1}{\sum_{0\le i\le n}{\left[ jc<ai+b-c+1 \right]}} \\ =\sum_{0\le j\le \lfloor \frac{an+b}{c} \rfloor -1}{\sum_{0\le i\le n}{\left[ ai>jc-b+c-1 \right]}} \\ =\sum_{0\le j\le \lfloor \frac{an+b}{c} \rfloor -1}{\sum_{0\le i\le n}{\left[ i\ge \lfloor \frac{jc-b+c-1}{a} \rfloor \right]}} \\ =\sum_{0\le j\le \lfloor \frac{an+b}{c} \rfloor -1}{n-\sum_{0\le i\le n}{\left[ i<\lfloor \frac{jc-b+c-1}{a} \rfloor \right]}} \\ =n\times \left( \lfloor \frac{an+b}{c} \rfloor \right) -\sum_{0\le j\le \lfloor \frac{an+b}{c} \rfloor -1}{\lfloor \frac{jc-b+c-1}{a} \rfloor} \\ =n\times \left( \lfloor \frac{an+b}{c} \rfloor \right) -f\left( \lfloor \frac{an+b}{c} \rfloor -\text{1,}c,-b+c-\text{1,}a \right) \\ \text{边界条件:} \\ f\left( \text{0,}a,b,c \right) =\lfloor \frac{b}{c} \rfloor \\ f\left( n,a,b,c \right) \left( a\ge c\text{或}b\ge c \right) =\sum_{0\le i\le n}{\lfloor \frac{ai+b}{c} \rfloor} \\ =\sum_{0\le i\le n}{\lfloor \frac{ai}{c}+\frac{b}{c} \rfloor} \\ =\sum_{0\le i\le n}{\lfloor \left( \lfloor \frac{a}{c} \rfloor +\frac{a-c\lfloor \frac{a}{c} \rfloor}{c} \right) i+\lfloor \frac{b}{c} \rfloor +\frac{b-c\lfloor \frac{b}{c} \rfloor}{c} \rfloor} \\ =\sum_{0\le i\le n}{\lfloor \frac{\left( a\,\,\text{mod }c \right) i+b\,\,\text{mod }c}{c} \rfloor +i\lfloor \frac{a}{c} \rfloor +\lfloor \frac{b}{c} \rfloor} \\ =\frac{n\left( n+1 \right)}{2}\lfloor \frac{a}{c} \rfloor +\lfloor \frac{b}{c} \rfloor \left( n+1 \right) +\sum_{0\le i\le n}{\lfloor \frac{\left( a\,\,\text{mod }c \right) i+b\,\,\text{mod }c}{c} \rfloor} \\ =\frac{n\left( n+1 \right)}{2}\lfloor \frac{a}{c} \rfloor +\lfloor \frac{b}{c} \rfloor \left( n+1 \right) +f\left( n,a\,\,\text{mod }c,b\,\,\text{mod }c,c \right) \\ \text{复杂度}O\left( \log N \right) $$

#include <assert.h>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <vector>

using int_t = long long int;
using std::cin;
using std::cout;
using std::endl;
int_t n, m;
struct Result {
    int_t x, y, pos;
};

int_t gcd(int_t a, int_t b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}
//��ȡб��Ϊy/x��ֱ���������ڵ��������
int_t getCountOnLine(int_t x, int_t y, int_t n, int_t m) {
    return std::min(n / x, m / y);
}
int_t fx(int_t n, int_t a, int_t b, int_t c) {
    if (n < 0) return 0;
    if (n == 0) return b / c;
    if (a >= c || b >= c) {
        return fx(n, a % c, b % c, c) + (n * (n + 1) / 2 * (a / c)) +
               (n + 1) * (b / c);
    } else {
        if (a == 0)
            return 0;
        else {
            return n * ((a * n + b) / c) -
                   fx((a * n + b) / c - 1, c, c - b - 1, a);
        }
    }
}
// x��1��n�ڣ�y��1��m�ڣ�������a/b�ķ�������
int_t getCount(int_t a, int_t b, int_t n, int_t m) {
    int_t d = (m * a) / b + ((m * a) % b != 0);
    int_t c = std::min(n, d - 1);
    int_t result = c * m - (fx(c, b, 0, a)) + getCountOnLine(a, b, n, m);
    return result;
}
Result walk(int_t n, int_t m, int_t k) {
    const auto check = [&](int_t a, int_t b) -> int_t {
        //���Ϸ�
        if (a > n || b > m) return 2;
        int_t under = getCount(a, b, n, m);
        int_t line = getCountOnLine(a, b, n, m);
        // a/b��С
        if (k > under) return -1;
        // a/b����
        else if (k < under - line + 1)
            return 1;
        else
            return 0;
    };
    //��ǰ������Ҳ�ķ���
    int_t leftA = 0, leftB = 1, rightA = 1, rightB = 0;
    int_t A, B;
    while (true) {
        int_t nextA = leftA + rightA;
        int_t nextB = leftB + rightB;
        int_t x = check(nextA, nextB);
        if (x == 0) {
            A = nextA;
            B = nextB;
            break;
        }
        int_t left = 1, right = n;
        int_t result = 0;
        //���ұ�������
        if (x < 0) {
            while (left <= right) {
                int_t mid = (left + right) / 2;
                if (check(leftA + mid * rightA, leftB + mid * rightB) < 0) {
                    left = mid + 1;
                    result = mid;
                } else {
                    right = mid - 1;
                }
            }
            leftA += result * rightA;
            leftB += result * rightB;

        } else {
            //������
            while (left <= right) {
                int_t mid = (left + right) / 2;
                if (check(rightA + mid * leftA, rightB + mid * leftB) == 1) {
                    left = mid + 1;
                    result = mid;
                } else {
                    right = mid - 1;
                }
            }
            rightA += result * leftA;
            rightB += result * leftB;
        }
    }
    int_t under = getCount(A, B, n, m) - getCountOnLine(A, B, n, m);
    k -= under;
    return Result{A * k, B * k};
}
void query(int_t n, int_t m, int_t k) {
    if (k <= m - 1) {
        printf("%lld %lld\n", 1ll, k + 1);
    } else if (k > (n * (m - 1))) {
        printf("%lld %lld\n", k - (n * (m - 1)) + 1, 1ll);
    } else {
        auto result = walk(n - 1, m - 1, k - (m - 1));
        printf("%lld %lld\n", result.x + 1, result.y + 1);
    }
}
int main() {
    // while (true) {
    //     int_t a, b, n, m;
    //     cin >> a >> b >> n >> m;
    //     cout << getCount(a, b, n, m) << endl;
    // }
    int T;
    scanf("%d", &T);
    while (T--) {
        int_t n, m, k;
        scanf("%lld%lld%lld", &n, &m, &k);
        query(n, m, k);
    }

    return 0;
}