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\)