Wipe Your Whiteboards

You walk into an empty classroom to do some homework and find that someone did not clean the whiteboard properly. The previous class in that room was about the extended Euclidean algorithm, because the board is covered with intermediate results of that algorithm. Parts of it have been wiped out, so you do not see everything they did. In particular, you cannot tell which numbers they used as the inputs. You did not feel like doing your homework anyway, so you decide to work out the numbers they started with.

From the intermediate results left on the board you know one thing for certain. Their inputs were integers $A$ and $B$ ($A, B \ge 1$), and the three integers $R$, $S$ and $Q$ still on the board ($R \ge 2$, $S \le -2$, $Q \ge 1$) satisfy $A \cdot R + B \cdot S = Q$. Given these three numbers, work out $A$ and $B$. Several pairs can fit the equation, so look for the pair with the smallest positive $A$ and $B$. You do not require $R$, $S$ and $Q$ to be genuine intermediate results of the extended Euclidean algorithm applied to $A$ and $B$. The equation $A \cdot R + B \cdot S = Q$ alone is enough.

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

Each test case is one line with three space-separated integers $R$, $S$ and $Q$. They satisfy $2 \le R \le 10^8$, $-10^8 \le S \le -2$ and $1 \le Q \le 10^8$. $Q$ is a multiple of the greatest common divisor of $R$ and $S$.

For each test case, print one line with two space-separated integers $A \ge 1$ and $B \ge 1$, the smallest pair with $A \cdot R + B \cdot S = Q$. The smallest pair is the one whose $A$ is minimal, and if several pairs share that $A$, the one among them whose $B$ is minimal.