题目描述

33DAI 在研究分数化成小数之后的规律。给定分数 $\frac{p}{q}$（$1 \le p < q$），把它写成小数；如果它是有限小数，就在末尾补 $0$ 看成无限小数（例如 $\frac{1}{2} = 0.5000\ldots$，$\frac{1}{4} = 0.25000\ldots$）。

小数部分从某一位开始一定会周期性地重复。33DAI 用两个数来描述这件事：

• 循环起点 $s$：从第 $s$ 位开始，小数部分按某个长度重复，并且 $s$ 是满足这一点的最小正整数；
• 循环节长度 $L$：在 $s$ 取到最小的前提下，使"从第 $s$ 位开始每隔 $L$ 位都相同"成立的最小正整数。

形式化地说：$s$ 是使"存在正整数 $L$，对任意 $i \ge s$ 都有第 $i$ 位数字与第 $i + L$ 位数字相同"成立的最小正整数；确定 $s$ 之后，$L$ 取满足该条件的最小正整数。

给定 $t$ 组 $p, q, k$，33DAI 想知道每组中：

• 小数部分第 $k$ 位上的数字；
• 循环起点 $s$；
• 循环节长度 $L$。

输入格式

从标准输入读入数据。

输入的第一行是一个整数 $t$（$1 \le t \le 10$），表示询问的个数。

接下来 $t$ 行，每行三个整数 $p, q, k$（$1 \le p < q \le 10^6$，$1 \le k \le 10^{18}$）。

输出格式

输出到标准输出。

输出 $t$ 行，顺序与输入一致。每行三个整数 $d, s, L$，用一个空格隔开，依次表示第 $k$ 位上的数字、循环起点、循环节长度。

3
1 3 1
1 2 1
1 7 5

3 1 1
5 2 1
5 1 6

3
5 6 3
1 6 10
1 28 1

3 2 1
6 2 1
0 3 6

2
1 4 13
1 999983 1000000000000000000

0 3 1
1 1 999982

样例解释

• 样例 1：$\frac{1}{3} = 0.3333\ldots$，第 $1$ 位是 $3$，从第 $1$ 位起重复的段是 3，所以起点 $1$、长度 $1$。$\frac{1}{2} = 0.5000\ldots$，第 $1$ 位是 $5$，从第 $2$ 位起重复的段是 0，所以起点 $2$、长度 $1$。$\frac{1}{7} = 0.142857142857\ldots$，第 $5$ 位是 $5$，循环节是 142857，所以起点 $1$、长度 $6$。
• 样例 2：$\frac{5}{6} = 0.8333\ldots$，第 $3$ 位是 $3$，从第 $2$ 位起重复的段是 3，所以起点 $2$、长度 $1$。$\frac{1}{6} = 0.1666\ldots$，第 $10$ 位是 $6$，起点 $2$、长度 $1$。$\frac{1}{28} = 0.035714285714\ldots$，第 $1$ 位是 $0$，从第 $3$ 位起是 571428 的重复，所以起点 $3$、长度 $6$。
• 样例 3：$\frac{1}{4} = 0.25000\ldots$，第 $13$ 位是 $0$，从第 $3$ 位起重复的段是 0，所以起点 $3$、长度 $1$。$\frac{1}{999983} = 0.000001000017\ldots$ 是纯循环小数，循环节长度是 $999982$，所以起点是 $1$；第 $10^{18}$ 位上的数字是 $1$。

提示

• 输出每行三个整数，用单个空格隔开。
• 循环起点与循环节长度都按"小数点后第几位"从 $1$ 开始编号。
• $q$ 最大是 $10^6$，$k$ 最大是 $10^{18}$。

数据范围

对于所有测试数据，保证 $1 \le t \le 10$，$1 \le p < q \le 10^6$，$1 \le k \le 10^{18}$。

共 $15$ 个测试点，按测试点计分：子任务 $1$、$2$ 的每个测试点 $6$ 分，子任务 $3$ 的每个测试点 $8$ 分。