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$.
Input
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.
Output
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}$.