Number Transformation

2000ms

524288K

Description:

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.

Sample Input:

Sample Output:

2 5
3 1
0 0

Informação

Provedor Codeforces

Código CF1674A