You are given two integers $x$ and $y$. You want to choose two strictly positive (greater than zero) integers $a$ and $b$, and then apply the following operation to $x$ exactly $a$ times: replace $x$ with $b \cdot x$.

You want to find two positive integers $a$ and $b$ such that $x$ becomes equal to $y$ after this process. If there are multiple possible pairs, you can choose any of them. If there is no such pair, report it.

For example:

• if $x = 3$ and $y = 75$, you may choose $a = 2$ and $b = 5$, so that $x$ becomes equal to $3 \cdot 5 \cdot 5 = 75$;
• if $x = 100$ and $y = 100$, you may choose $a = 3$ and $b = 1$, so that $x$ becomes equal to $100 \cdot 1 \cdot 1 \cdot 1 = 100$;
• if $x = 42$ and $y = 13$, there is no answer since you cannot decrease $x$ with the given operations.

Input

The first line contains one integer $t$ ($1 \le t \le 10^4$) — the number of test cases.

Each test case consists of one line containing two integers $x$ and $y$ ($1 \le x, y \le 100$).

Output

If it is possible to choose a pair of positive integers $a$ and $b$ so that $x$ becomes $y$ after the aforementioned process, print these two integers. The integers you print should be not less than $1$ and not greater than $10^9$ (it can be shown that if the answer exists, there is a pair of integers $a$ and $b$ meeting these constraints). If there are multiple such pairs, print any of them.

If it is impossible to choose a pair of integers $a$ and $b$ so that $x$ becomes $y$, print the integer $0$ twice.

Samples

3
3 75
100 100
42 13

2 5
3 1
0 0