969 . Integer Game
Description
You are playing a single player game where you can convert one integer from another through a sequence of moves. The integer Y is reachable from X in a single move if the following is satisfied.
Y = X * P2k / P1k
where k is a positive integer, P2 and P1 are prime numbers and X is divisible by P1k.
For example 18 is reachable from 8 in one move, because you can divide 8 by 4 and then multiply by 9. But 6 is not reachable from 8. Given two integers A and B calculate the minimum number of moves necessary to transform A into B. Both A and B can be very large. So each of them is needed to be expressed as a multiplication of a sequence of small integers:
Both of the sequences ai and bi will be given as inputs.
Input Format
First line of the input contains T (1 ≤ T ≤ 200) the number of test cases. Then T blocks of test cases follows. First line of the test case contains N (1 ≤ N ≤ 300) followed by N integers. N is the length of the sequence ai and the following N integers form the sequence ai. The second line starts with an integer M (1 ≤ M ≤ 300). M is the length of the sequence bi and the following M integers form the sequence bi. Each of integers in these two sequences will be between 2 and 200 (inclusive).
Output Format
For each case of input, print the serial of output followed by an integer: the minimum number of moves required to transform A to B. If it is impossible to transform A to B with any number of moves output -1 instead. If the minimum number of moves is greater than or equal to 20 print a -1 as well.
Sample Input 1
4 1 4 1 9 2 2 2 2 3 3 1 8 1 6 2 32 11 3 27 25 13
Sample Output 1
Case 1: 1 Case 2: 1 Case 3: -1 Case 4: 3
Hints
Problem Source
Migrated from old NTUJ.
icpc regional 2009, dhaka site
Subtasks
| No. | Testdata Range | Score |
|---|