题目描述

吃过草莓刨冰之后，Vani 和 cl 有些疲倦地坐在一个长椅上。

“呐，玩得开心吗？”Vani 忽然问道。

“嗯……很，很开心的说。”

“那么，我有一个问题想要问你呢。”

cl 的脸有点红了起来。

“嗯……好吧。问、问吧……我会告诉你的哦……”

“那好。对于一个分数 $\displaystyle \frac{a}{b}$……”

“嗯……哎？哎？！”

“……就是这个问题。我觉得这个问题好纠结啊……”

Vani 淡定地说完这句话。

“啊？！哈啊？！”

对于给定的分数 $\displaystyle \frac{a}{b}$，求其在 $k$ 进制下是有限小数还是循环小数。如果是有限小数，求小数点后的位数；如果是循环小数，则求混循环部分和循环节的长度又分别是多少。

注意，循环节指的是最短循环节，且混循环部分的长度也指最短。

输入格式

第一行一个正整数 $T$，表示测试数据的数目。

每个测试数据包含三个空格分隔的整数 $a,b,k$。含义如题目所示。

输出格式

对于每个测试数据，在单独的一行内输出两个空格分隔的整数 $m, r$。

其中 $m$ 表示混循环部分的长度，$r$ 表示循环节的长度。 如果 $\displaystyle \frac{a}{b}$ 在 $k$ 进制下是有限小数，则 $r=0$，$m$ 为小数点后面的位数；如果 $\displaystyle \frac{a}{b}$ 在 $k$ 进制下是纯循环小数，则 $m=0$。

样例输入

3
1 8 10
17 99 10
217 990 10

样例输出

3 0
0 2
1 2

数据规模与约定

对于 $100\%$ 的数据，$1\leq a<b\leq 10^{12}$，$k\leq 10^{12}$，$T\leq 10$。

题目来源

Poetize2