Cho mảng \(A\) có \(n\) phần tử và \(q\) câu truy vấn, mỗi câu chứa một giá trị \(x\). Hỏi: có bao nhiêu đoạn con \([L,R]\) mà có \(gcd(a_l,a_{l+1}...a_r)=x\) bằng đúng giá trị \(x\) của câu truy vấn.

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên \(n\) \((1 \le n \le 10^5)\)
• Dòng tiếp theo chứa \(n\) phần tử của mảng \(A\) \((1 \le a_i \le 10^9)\)
• Dòng thứ ba chứa \(q\) (\(1 \le q \le 3 \times 10^5\)) là số lượng truy vấn. \(q\) dòng tiếp theo, mỗi dòng sẽ chứa một số nguyên \(x\) \(1 \le x \le 10^9\)

Dữ liệu ra

• In ra đáp án của mỗi câu truy vấn

Input 1

3
2 6 3
5
1
2
3
4
6

Output 1

1
2
2
0
1