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 × P 2k P1k where k is a positive integer, P1 and P2 are prime numbers and X is divisible 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 ∏∏ 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 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 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 4 14 19 222 233 18 16 2 32 11 3 27 25 13 Sample Output Case 1: 1 Case 2: 1 Case 3: -1 Case 4: 3 to be expressed as a multiplication of a sequence of small integers: A = Ni=1 a1 and B = Mi=1 b1 Both of the sequences ai and bi will be given as inputs.