Hiiragi likes collecting sticks. It is said that she has collected m short sticks. One day, she was very excited that she found more sticks from a box under her bed. These new sticks have n different lengths, while for each length, there are infinite sticks of the same length.
Hiiragi then came up with an idea, that concatenates the new sticks in different ways to form long sticks of all possible lengths no longer than L. Let's name the lengths a set S. Her mother told her that "Use each of your m short sticks to measure each of the lengths in S. When you find a short sticks being able to measure a length in integer times, get the times it takes and denote it as t. I will give you one candy if you can find one way that uses the following rules to reduce t to 1."
For a number t, find one of its prime factor p, calculate t1 = t / p.
Use t1 as the new t and go back to the first step until t reaches 1.
Note: With the same short stick and the same length in S, two ways are considered to be different iff the reduce processes are not all the same. But it may be counted many times if it's another short stick or the length differs.
So here, you are required to calculate how many candies Hiiragi can get at most.
Input
The first line is T ( ≤ 10), the number of test cases.
Next is T test cases. Each case contains 3 lines. The first line contains three integers n, m, L (n ≤ 20, m ≤ 105, L ≤ 106). The second line is n integers indicating the lengths of each kind of sticks found under the bed. The third line is m integers indicating the sticks Hiiragi originally had. All sticks have length no shorter than 1 and no longer than L.
Output
For each case, print one integer, the number of candies Hiiragi can get at most.
Sample Input
1
2 4 12
4 6
1 3 4 3
Sample Output
16
