408048: GYM102966 L Lets Count Factors

Planet E-13 orbits around a star in a faraway galaxy named UAZ. All University students in that planet need to know well how to perform prime factorization on numbers, otherwise they risk failing the courses they take. One of the teachers likes asking the students in his class the following question: how many different prime numbers must be multiplied together (maybe some of them more than once) to obtain the same result as the product of a pair of the given numbers $$$A$$$ and $$$B$$$?

Thanitos is a student taking such course and he is really nervous; he does not want to fail. Your task is to help Thanitos answer $$$N$$$ teachers question.

The first line contains the number $$$N$$$ ($$$1 \leq N \leq 10^5$$$) of questions that the teacher will make. Each of the following $$$N$$$ lines will contain a question the teacher makes and it consists of the numbers $$$A$$$ and $$$B$$$ ($$$1 \leq A, B \leq 10^7$$$) separated by a space.

For each teacher question print a line with a number representing how many different prime numbers must be multiplied to obtain A*B (the product of A and B).

5
13 17
120 980
43 1
60 1
78 11

2
4
1
3
4