504054 - K进制下的分数

【题目描述】K进制下的分数(K)

对于给定的分数 A/B,求其在K进制下是有限小数还是循环小数。如果是有限小数,求小数点后的位数;如果是循环小数,则求混循环部分和循环节(repetend)的长度又分别是多少。

输入

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

输出

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

样例

输入

3
1 8 10
17 99 10
217 990 10

输出

3 0
0 2
1 2

提示

【数据规模】 对于50%的数据,B≤100000。 对于100%的数据,1≤A≤10^18,2≤K≤10^18,1≤B≤2×10^6

时间限制 1 秒
内存限制 128 MB
统计
上一题 下一题