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.
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.
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.
Input | Output |
---|---|
2 4 2 2 2 4 4 2 2 1 2 | Case 1: 8 Case 2: 16 |