### 问题描述 在一个充满了魔法的世界中，小桥是一名积极向上的杰出魔法师。 他最近在研究一种用于转化魔法元素的实验方法，他一共进行了 $n$ 次实验。这个实验需要两种不同的魔法元素 $a$ 和 $b$，以及一种特殊的催化剂 $c$。小桥发现，他可以通过以下两种方法使用催化剂 $c$ 改变这两种元素： - 选取某种催化剂 $c$ ($c > 1$，并且 **元素 $a$ 应当可以被 $c$ 整除**），然后将元素 $a$ 转化为 $\frac{a}{c}$； - 选取某种催化剂 $c$ ($c > 1$，并且 **元素 $b$ 应当可以被 $c$ 整除**），然后将元素 $b$ 转化为 $\frac{b}{c}$。 小桥的目标是在恰好 $k$ 次实验后使得魔法元素 $a$ 和 $b$ 完全相同。 在给定魔法元素 $a$ 和 $b$，以及实验次数 $k$ 的情况下，你的任务是算出 $t$ 次实验的成功率是多少。 ### 输入格式 第一行包含一个整数 $n$ ($1 \le n \le 10^4$)，表示小桥进行的实验组数。 接下来的 $t$ 行，每行包含三个整数 $a$，$b$ 和 $k$ ($1 \le a, b, k \le 10^9$)，分别代表一组实验中的两种魔法元素和实验次数。 ### 输出格式 两个整数，形如 `x y` 表示 $\frac xy$，若成功率为 $0$，则输出 `0 1`。 ### 样例输入 ```text 5 1 2 1 2 3 2 3 4 3 4 5 4 5 6 5 ``` ### 样例输出 ```text 3 5 ```