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。

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