Migrated from Lutece 2110 GCD Intervals

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

Bob has a sequence {$a_1,a_2,...,a_n$}, he wants to count how many intervals $[l,r]$ $(l\le r)$ have the same greatest common divisor $x_i$. Because it is too slow to enumerate all the intervals one by one, please help him. For instance, with regard to sequence {1，2，3，4},1 is the greatest common divisor of interval [1,1], [1,2], [1,3], [1,4], [2,3], [2,4], [3,4], so the answer is 7.

Input

In the first line there is an integer T, indicating the number of test cases. Then 3*T lines follow. In each test case, there are 3 lines. The first line contains 2 numbers. n is the length of the sequence, m is the number of queries. $(n\le1e5,m\le1e5)$ The second line contains n integers, the sequence {$a_i$} $(1\le a_i \le 1e9)$ The third line contains m integers, {$x_i$} is each query of sequence{$a_1,a_2,...,a_n$} $(1\le x_i \le 1e9)$ The sum of n is less than 3e5, the sum of m is less than 3e5

Output

There are T lines, in each line, output the answer of each query, there is a " " after each number

Samples

1
4 4
1 2 3 4
1 2 3 4

7 1 1 1