Strange Definition

Description:

Input:

The first input line contains a single integer $$$t$$$ ($$$1 \le t \le 10^5)$$$ — the number of test cases.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 3 \cdot 10^5$$$) — the length of the array.

The following line contains $$$n$$$ integers $$$a_1, \ldots, a_n$$$ ($$$1 \le a_i \le 10^6$$$) — array elements.

The next line contain a single integer $$$q$$$ ($$$1 \le q \le 3 \cdot 10^5$$$) — the number of queries.

The following $$$q$$$ lines contain a single integer $$$w$$$ each ($$$0 \le w \le 10^{18}$$$) — the queries themselves.

It is guaranteed that the sum of values $$$n$$$ over all test cases does not exceed $$$3 \cdot 10^5$$$, and the sum of values $$$q$$$ over all test cases does not exceed $$$3 \cdot 10^5$$$

Output:

For each query output a single integer — the beauty of the array at the corresponding moment.

Sample Input:

2
4
6 8 4 2
1
0
6
12 3 20 5 80 1
1
1

Sample Output:

2
3

Note:

In the first test case, the initial array contains elements $$$[6, 8, 4, 2]$$$. Element $$$a_4=2$$$ in this array is adjacent to $$$a_4=2$$$ (since $$$\frac{lcm(2, 2)}{gcd(2, 2)}=\frac{2}{2}=1=1^2$$$) and $$$a_2=8$$$ (since $$$\frac{lcm(8,2)}{gcd(8, 2)}=\frac{8}{2}=4=2^2$$$). Hence, $$$d_4=2$$$, and this is the maximal possible value $$$d_i$$$ in this array.

In the second test case, the initial array contains elements $$$[12, 3, 20, 5, 80, 1]$$$. The elements adjacent to $$$12$$$ are $$$\{12, 3\}$$$, the elements adjacent to $$$3$$$ are $$$\{12, 3\}$$$, the elements adjacent to $$$20$$$ are $$$\{20, 5, 80\}$$$, the elements adjacent to $$$5$$$ are $$$\{20, 5, 80\}$$$, the elements adjacent to $$$80$$$ are $$$\{20, 5, 80\}$$$, the elements adjacent to $$$1$$$ are $$$\{1\}$$$. After one second, the array is transformed into $$$[36, 36, 8000, 8000, 8000, 1]$$$.