Solve This Giveaway Problem First

This problem is straightforward and easy. You will be given two integers N, P and a list L of positive integers.

You have to count how many numbers in the range [1, NP] are divisible by at least one of the numbers from the list L.

Input

The first line of the input will contain an integer T. Then there will be T test cases.
The first line of each case will contain two integer numbers N and P.
The second line of each case will contain an integer S, size of the list L.
The third line of each case will contain S space-separated positive integer numbers.

1 <= T <= 105
1 <= N <= 10100000
1 <= P <= 105
1 <= S <= 5
1 <= numbers in the list L <= 109

N.B: It is guaranteed that multiplication of all numbers in the list L will not exceed 109 and the summation of the length of number N over all test cases will not exceed 106.

Output

For each test case, print "Case x: y" (without quotation marks) where x is the test case number and y is the required answer modulo 1000000007.

See the sample input-output for better understanding.

Sample

Input	Output
2 4 2 2 2 4 4 2 2 1 2	Case 1: 8 Case 2: 16