背景

吃过草莓刨冰之后,Vani 和 cl 有些疲倦地坐在一个长椅上。 “呐,玩得开心吗?”Vani 忽然问道。 “嗯……很,很开心的说。” “那么,我有一个问题想要问你呢。”

cl 的脸有点红了起来。 “嗯……好吧。问、问吧……我会告诉你的哦……” “那好。对于一个分数 A / B……” “嗯……哎?哎?!” “……就是这个问题。我觉得这个问题好纠结啊……” Vani 淡定地说完这句话。
“啊?!哈啊?!”

题目描述

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

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

输入格式

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

输出格式

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

在 K 进制下是纯循环小数,则 M = 0。 样例输入

样例输出

3 0

0 2

1 2

数据范围与约定

对于 50% 的数据,B≤100000。
对于 100% 的数据,1≤A<B≤1012,K≤1012,T≤10。

题解

暴力完我就不会了