Description

吃过草莓刨冰之后，Vani和cl有些疲倦地坐在一个长椅上。 　　“呐，玩得开心吗？”Vani忽然问道。 　　“嗯……很，很开心的说。” 　　“那么，我有一个问题想要问你呢。” 　　cl的脸有点红了起来。 　　“嗯……好吧。问、问吧……我会告诉你的哦……” 　　“那好。对于一个分数A / B……” 　　“嗯……哎？哎？！” 　　“……就是这个问题。我觉得这个问题好纠结啊……” 　　Vani淡定地说完这句话。 　　“啊？！哈啊？！”

对于给定的分数 A / B，求其在 K 进制下是有限小数还是循环小数。如果是有限小数，求小数点后的位数；如果是循环小数，则求混循环部分和循环节的长度又分别是多少。 　　注意，循环节指的是最短循环节，且混循环部分的长度也指最短。

Format

Input

第一行一个正整数 T，表示测试数据的数目。 　　每个测试数据包含三个空格分隔的整数 A, B, K。含义如题目所示。

Output

对于每个测试数据，在单独的一行内输出两个空格分隔的整数 M, R。 　　其中 M 表示混循环部分的长度，R 表示循环节的长度。 　　如果 A / B 在 K 进制下是有限小数，则 R = 0，M 为小数点后面的位数；如果 A / B 在 K 进制下是纯循环小数，则 M = 0。

Samples

3
1 8 10
17 99 10
217 990 10

3 0
0 2
1 2

Limitation

对于 100% 的数据，1≤A<B≤10^12，K≤10^12，T≤10。