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