有限小数

题目描述

给定两个互质正整数$a$,$b$，你需要求两个非负整数$c$,$d$，满足以下两个条件： • $\frac{a}{b}+\frac{c}{d}$为十进制下的整数或有限小数。 • $1 \le d \le 10^9$ 。 在所有满足条件的非负整数对$(c,d)$中，请求出$c$最小的一对。 一个有理数$x$是十进制下的有限小数，当且仅当将$x$在十进制下以小数形式写出 后，小数点后的位数是有限的，即存在正整数k，整数p和整数数组$(q_1,q_2,...,q_k)$满 足$0\le q_i\le 9$，使得$x=p+ \sum^{k}_{i=1} q_i ·10^{-i}$。

输入格式

从标准输入读入数据。 第一行包含一个正整数$T(1\le T\le 10^4)$，表示数据组数。 每组数据包含一行两个正整数$a$,$b(1\le a b\le 10^6)$，含义如题目描述所示。保证 $gcd(a,b)=1$。

输出格式

输出到标准输出。 对于每组数据，输出一行两个非负整数$c$,$d$。如果有多组正确答案，输出任意一组 即可。

样例 #1

样例输入 #1

4
1 2
2 3
3 7
19 79

样例输出 #1

0 1
1 3
1 14
3 316

提示

对于第一组数据，由于$\frac{1}{2}=0.5$是有限小数，因此输出$(c,d)$满足$c=0$且$1\le d\le 10^9$ 即可。 对于第二组数据，$\frac23+\frac13 =1$是整数，且 $\frac 23 =0.666...$不是有限小数，因此$c=1$是 最小可能值。 对于第三组数据，$\frac37+ \frac{1}{14} = \frac12 =0.5$ 是有限小数。 对于第四组数据，$\frac{19}{79} + \frac{3}{316} = \frac1 4 =0.25$ 是有限小数，且可以证明不存在 $0\le c \le2$， $1\le d\le 10^9$使得 $\frac{19}{79} + \frac{c} {d}$ 是有限小数。