Given two coprime positive integers $a$ and $b$, you need to find two non-negative integers $c$ and $d$ that satisfy the following two conditions: $\frac{a}{b} + \frac{c}{d}$ is an integer or a finite decimal in base 10. $1 \le d \le 10^9$.

Among all pairs of non-negative integers $(c, d)$ that satisfy the conditions, find the one with the minimum $c$.

A rational number $x$ is a finite decimal in base 10 if and only if, when written in decimal form, the number of digits after the decimal point is finite. That is, there exists a positive integer $k$, an integer $p$, and an array of integers $(q_1, q_2, \dots, q_k)$ such that $0 \le q_i \le 9$, satisfying $x = p + \sum_{i=1}^{k} q_i \cdot 10^{-i}$.

Input

The input is read from standard input. The first line contains a positive integer $T$ ($1 \le T \le 10^4$), representing the number of test cases. Each test case consists of one line containing two positive integers $a$ and $b$ ($1 \le a \le b \le 10^6$), with meanings as described in the problem statement. It is guaranteed that $\gcd(a, b) = 1$.

Output

Output to standard output. For each test case, output one line containing two non-negative integers $c$ and $d$. If there are multiple correct answers, output any one of them.

Examples

Input 1

4
1 2
2 3
3 7
19 79

Output 1

0 1
1 3
1 14
3 316

Note

For the first test case, since $\frac{1}{2} = 0.5$ is a finite decimal, outputting $(c, d)$ such that $c = 0$ and $1 \le d \le 10^9$ is sufficient.

For the second test case, $\frac{2}{3} + \frac{1}{3} = 1$ is an integer, and $\frac{2}{3} = 0.666\dots$ is not a finite decimal, so $c = 1$ is the minimum possible value.

For the third test case, $\frac{3}{7} + \frac{1}{14} = \frac{1}{2} = 0.5$ is a finite decimal.

For the fourth test case, $\frac{19}{79} + \frac{3}{316} = \frac{1}{4} = 0.25$ is a finite decimal, and it can be proven that there exists no $0 \le c \le 2$ and $1 \le d \le 10^9$ such that $\frac{19}{79} + \frac{c}{d}$ is a finite decimal.