Problem Description

Xiao Ming is very curious about number theory and one day his teacher gives him a very strange homework. He is provided with $n$ positive integers $a_1, a_2, \ldots, a_n$ and it is guaranteed that all numbers will be no greater than $m$. What's more, his teacher asks him $k$ questions. Each time, the teacher gives a certain number $x$ (also no greater than $m$) and ask Xiao Ming for the number of pairs $(a_i,a_j)$ that satisfy $\gcd(a_i,a_j) = x$ where $1\leq i, j \leq n$.

That is to calculate
$$\sum_{i=1}^{n}\sum_{j=1}^{n}[\gcd(a_i,a_j)=x].$$

It is very difficult for Xiao Ming to figure out the problem and he turn to you for help.

Input

The first line of the input contains one integer $T(1\leq T \leq 10)$ - the number of test cases. Then $T$ test cases follows.

The first line of each test case contains three integers $n , m, k$ $(1\leq n, m, k\leq 10^5)$ as described above.

The second line contains $n$ integers $a_1,a_2,\ldots, a_n$ $(1 \leq a_i \leq m)$.

Each of next $k$ lines contains a single integer $x$.

Output

For each test case, print the answer in one line.

1
5 5 5
1 2 3 4 5
1
2
3
4
5

19
3
1
1
1