题目描述

小 F 在学习小数表示。

给出一个分数的分子和分母，小 F 想知道它是否是循环小数，以及它的循环节有多长。

10 进制的话小 F 也会，因此她希望你在 $k$ 进制下判断。

输入格式

第一行一个整数 $T$ ，表示测试数据组数。

接下来的 $T$ 行，每行三个整数 $p,q,k$ ，表示分子，分母和进制数。

输出格式

对于每组数据，输出一行两个整数。

若 $p/q$ 在 $k$ 进制下是有限小数，请输出 x 0 ，其中 $x$ 为小数点后面的位数。

若 $p/q$ 在 $k$ 进制下是循环小数，请输出 x y ，其中 $x$ 为混循环长度（即小数点后，开始循环之前的部分的位数）， $y$ 为循环节长度。

样例

3
1 8 10
217 990 10
17 99 10

3 0
1 2
0 2

$1/8=0.125$

$217/990=0.2(19)$

$17/99=0.(17)$

数据范围与约定

对于 $20\%$ 的数据， $q\leq 10^4$ 。

对于 $100\%$ 的数据， $T\leq 10,1\leq p,q,\leq 10^{12},2\leq k\leq 10^{12}$ 。