Good Numbers

Kyrie is a programmer highly interested in math. He likes to design math games for himself to play. One day, he defined that “a positive integer u is under good relation with another positive integer $v$” if the set of all prime factors of $u$ and the set of all prime factors of $v$ are the same. For example, 6 is under good relation with 12, since the set of all prime factors of both 6 and 12 are the same.

Now he has a number $k$, he tries to find all numbers that are under good relation with $k$. However, he then unfortunately discovers the fact that there are infinite integers which satisfy this condition. Therefore, Kyrie defines: For a positive integer $n$, if there exist an integer $T$ that satisfies $n · T = k$ and $n$ is under good relation with $k$ at the same time, then he will say “$n$ is good.”

Kyrie is now very happy seeing that there are only finite “good numbers” no matter what the value of k is. He decides to invite his friend Erik to play the math game together. They pick $k_1$ and $k_2$ and try to find their own “good number” accordingly. Assume there is a surprising miracle that $k_1$ and $k_2$ have the same greatest prime factor, and what’s more, second large prime factor of $k_1$ is not a factor of $k_2$ and the second large prime factor of $k_2$ is also not a factor of $k_1$.

Write a program to find out how many “good number” there are under $k_1$ and $k_2$.

The first line on the input contains an integer $T (T \leq 10)$. There will be $T$ test cases. For each test case, there are two positive integers $k_1$ and $k_2 (1 \leq k_1, k_2 ≤ 10^{24})$ will be given in a line.

Print two numbers to represent how many good numbers can the two people find in one line for each test case. It is guaranteed that the answer will not exceed $10^{18}$.

4
21 35
20 15
37128 32725
637000 707850

1 1
2 1
3 2
18 8

2015 ACM/ICPC Asia Regional Changchun Online