Background

The background is unrelated to the problem and can be skipped; you may read the description directly.

There is a kind of person called "someone else’s little sister", and Little A deeply relates to this.

Little A’s younger sister—Little L—often steals Little A’s stored books to read, which gives Little A a real headache.

This time, perfectionist Little A was tidying up his book collection, and Little L took one book while he was not paying attention.

"Give it back to me."

"No. But... if you can guess the ID number of the book in my hand, I will give it back to you."

To make it easier to take and organize his collection, Little A numbered every book starting from $1$.

"You must be joking. I have so many books—how can I guess?"

"Okay. Then I will tell you the average of the ID numbers of the remaining pile of books. How about that? Is this hint enough?"

"..."

Little A has so many books that he does not even know how many there are. But as a qualified OIer, with the help of a computer, Little A successfully computed the answer. However, he wants to use this problem to test you.

Problem Description

You are given the value of $\dfrac{\left(\sum\limits^{n}_ {i = 1}i \right) - m}{n - 1}$, where $m \in [1, n]$, and both $n$ and $m$ are positive integers. You need to determine the values of $n$ and $m$. A solution is guaranteed to exist.

If there are multiple feasible solutions, output the one with the smaller $n$.

Multiple test cases.

Input Format

The first line contains a positive integer $T$, the number of test cases.

The next $T$ lines each contain three non-negative integers $a, b, c$, meaning the average value is $a + \dfrac{b}{c}$.

Output Format

Output $T$ lines. Each line contains two positive integers, representing $n$ and $m$.

3
2 1 3
3 1 4
5 1 3

4 3
5 2
10 7

Hint

This problem uses bundled tests.

• Subtask 1 (5 points): $T \leqslant 10$, $n \leqslant 10^3$.
• Subtask 2 (5 points): $T \leqslant 10^3$, $n \leqslant 10^3$.
• Subtask 3 (5 points): $T \leqslant 10$, $n \leqslant 5\times 10^5$.
• Subtask 4 (40 points): $T \leqslant 10^3$, $n \leqslant 10^{18}$.
• Subtask 5 (45 points): No special constraints.

For all testdata, $1 \leqslant m \leqslant n \leqslant 10 ^ {18}$, $n \not = 1$, $1 \leqslant T \leqslant 2 \times 10 ^{5}$, $1 \leqslant a \leqslant 10 ^{18}$, $0 \leqslant b < c \leqslant 10 ^ {18}$.

It is guaranteed that $\dfrac{b}{c}$ is a reduced proper fraction. In particular, when $b=0$, $c=1$.

Background (continued)

"Y-you... how did you guess it?"

As Little L spoke, the surprise in her eyes at Little A gained an extra bit of admiration.

"Hah, how could a problem of this difficulty possibly stump me?"

"Ah. If that is the case, then let’s play one more time!"

"..."

Translated by ChatGPT 5