K |
Integer Game Input: Standard Input Output: Standard Output |
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.
, where k is a positive integer, and are prime numbers and X is divisible by.
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: and . Both of the sequences and will be given as inputs.
Input
First line of the input contains T (1 ≤ T ≤ 40) 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 and the following N integers form the sequence . The second line starts with an integer M (1 ≤ M ≤ 300). M is the length of the sequence and the following M integers form the sequence . Each of integers in these two sequences will be between 2 and 200 (inclusive).
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.
4 1 4 1 9 2 2 2 2 3 3 1 8 1 6 2 32 11 3 27 25 13 |
Case 1: 1 Case 2: 1 Case 3: -1 Case 4: 3
|
Problemsetter: Abdullah al Mahmud, Special Thanks: Arifuzzaman Arif