Hiiragi's Sticks

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

1个回答

Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
立即提问