Cho một dãy $A$ gồm $N$ số nguyên dương. Có $Q$ truy vấn, mỗi truy vấn cho số nguyên dương $X$, yêu cầu đếm số đoạn con $[l;r] (1≤l≤r≤N)$ mà ước chung lớn nhất của các số trong đoạn $[l;r]$ bằng $X$

Input:

• Dòng đầu tiên ghi số$N$.

• Dòng tiếp theo ghi dãy$N$ số nguyên của dãy $A$

• Dòng tiếp theo ghi số$Q$

• Dòng tiếp theo ghi $Q$số nguyên tương ứng với$Q$ truy vấn

Output:

• gồm $Q$ dòng, mỗi dòng ghi một số là số đoạn con thỏa mãn với truy vấn tương ứng.

Sample Input

3
2 6 3
5
1 2 3 4 6

Sample Output

1
2
2
0
1

Ràng buộc

$1 ≤ N, Q ≤ 10^5$

Các giá trị cho trong day$<=10^9$