题目描述

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

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

输入格式

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

每个测试数据包含三个空格分隔的整数 $\red{A, B, K}$。含义如题目所示。

输出格式

对于每个测试数据，在单独的一行内输出两个空格分隔的整数 $\red{M, R}$。

其中 $\red{M }$表示混循环部分的长度，$\red{R }$表示循环节的长度。

如果 $\red{A / B }$在 $\red{K }$进制下是有限小数，则 $\red{R = 0，}$$\red{M }$为小数点后面的位数；如果 $\red{A / B }$ 在 $\red{K }$进制下是纯循环小数，则 $\red{M = 0}$。

样例

输入样例

3
1 8 10
17 99 10
217 990 10

输出样例

3 0
0 2
1 2

提示

对于 $\red{50\% }$的数据，$\red{B≤}$$\red{100000}$。

对于 $\red{100\% }$的数据，$\red{1≤}$$\red{A<B≤}$$\red{10^{12}，}$$\red{K≤}$$\red{10^{12}，}$$\red{T≤}$$\red{10}$。