只要努力飞翔，即使再弱小的蝴蝶也可以飞的很高
504054 - K进制下的分数
【题目描述】K进制下的分数（K）
对于给定的分数 A/B，求其在K进制下是有限小数还是循环小数。如果是有限小数，求小数点后的位数；如果是循环小数，则求混循环部分和循环节（repetend）的长度又分别是多少。
Input
第一行一个正整数T，表示测试数据的数目。 每个测试数据包含三个空格分隔的整型整数 A，B，K。
Output
对于每个测试数据，在单独的一行内输出两个空格分隔的整数 M和R。 其中M表示混循环部分的长度，R表示循环节的长度。 如果A/B在K进制下是有限小数，则R＝0，M为小数点后面的位数；如果A/B在K进制下是纯循环小数，则 M＝0。
Examples
Input
3 1 8 10 17 99 10 217 990 10
Output
3 0 0 2 1 2
Hint
【数据规模】 对于50%的数据，B≤100000。 对于100%的数据，1≤A≤10^18，2≤K≤10^18，1≤B≤2×10^6。