题目描述

给定两个互质正整数 $a$ 和 $b$，你需要求两个非负整数 $c$ 和 $d$，满足以下两个条件：

• $\frac{a}{b} + \frac{c}{d}$ 为十进制下的整数或有限小数。
• $1 \leq d \leq 10^9$。

在所有满足条件的非负整数对 $(c, d)$ 中，请求出 $c$ 最小的一对。

一个有理数 $x$ 是十进制下的有限小数，当且仅当将 $x$ 在十进制下以小数形式写出后，小数点后的位数是有限的，即存在正整数 $k$，整数 $p$ 和整数数组 $(q_1, q_2, \dots, q_k)$ 满足 $0 \leq q_i \leq 9$，使得：

输入格式

从标准输入读入数据。

第一行包含一个正整数 $T$ ($1 \leq T \leq 10^4$)，表示数据组数。

每组数据包含一行两个正整数 $a, b$ ($1 \leq a \leq b \leq 10^6$)，含义如题目描述所示。保证 $\text{gcd}(a, b) = 1$。

输出格式

输出到标准输出。

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

样例

4
1 2
2 3
3 7
19 79

0 1
1 3
1 14
3 316

样例解释

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