All submissions for this problem are available.
You are given two numbers A and B. You need to convert A into B by a certain set of operations. An operation is defined as one among the following :
- multiplying the number by a prime number
- dividing the number by a prime number
- multiplying the number by a perfect square which has the same number of each prime factor in it's prime factorization
Now, given A and B, find the minimum number of operations required to convert A to B.
Input format :
First line consists of t, the number of test cases (1 <= t <= 100)
Next t lines consist of two space separated integers A and B ( 1 <= A, B <= 1000000000)
Output format :
For each test case, print one line containing the minimum number of operations to convert A to B.
Sample input :
Sample output :
|Time Limit:||0.1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.