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.
输入解释
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$.
输出解释
For each test case, print the answer in one line.
Hint
For $i\neq j$, $(a_i,a_j)$ and $(a_j,a_i)$ are considered different.