One day, Peter came across a function which looks like:

`F`(1,`X`) =`X`mod`A`_{1}.`F`(`i`,`X`) =`F`(`i`- 1,`X`) mod`A`, 2 ≤_{i}`i`≤`N`.

Peter wants to know the number of solutions for equation `F`(`N`, `X`) = `Y`, where `Y` is a given number.

There are multiple test cases. The first line of input contains an integer `T`, indicating the number of test cases. For each test case:

The first line contains two integers `N` and `M` (2 ≤ `N` ≤ 10^{5}, 0 ≤ `M` ≤ 10^{9}).

The second line contains `N` integers: `A _{1}`,

The third line contains an integer `Q` (1 ≤ `Q` ≤ 10^{5}) - the number of queries. Each of the following `Q` lines contains an integer `Y _{i}` (0 ≤

提交代码