Thử thách GCD của Alice và Bob

Alice và Bob là hai người bạn thân, nhưng họ luôn thích thách thức nhau bằng các bài toán hóc búa. Vào một buổi chiều mưa, Bob đã đưa ra một thử thách mới và cực kỳ khó nhằn cho Alice. Anh ta đưa cho Alice một dãy số và yêu cầu cô phải giải quyết một loạt các truy vấn phức tạp. Đây không phải là bài toán đơn giản, vì nó liên quan đến kiến thức chuyên sâu về lý thuyết số và đặc biệt là ước số chung lớn nhất (GCD).

Bob, một "bậc thầy thách đố", đã nghĩ ra thử thách này sau nhiều ngày suy nghĩ. Alice, được biết đến như một "nữ hoàng toán học", đã chấp nhận ngay lập tức với quyết tâm chứng minh rằng không có thử thách nào có thể làm khó cô. Tuy nhiên, để vượt qua bài toán này, Alice cần đến sự giúp đỡ từ bạn --- một nhà lập trình tài ba và có kiến thức sâu về thuật toán.

Cho một dãy số nguyên \(a_1, a_2, \ldots, a_n\), và có \(q\) truy vấn \(x_1, x_2, \ldots, x_q\). Đối với mỗi truy vấn \(x_i\), bạn cần đếm số lượng cặp \((l, r)\) sao cho \(1 \leq l \leq r \leq n\) và \(\gcd(a_l, a_{l+1}, \ldots, a_r) = x_i\).

Trong đó, \(\gcd(v_1, v_2, \ldots, v_n)\) là ước số chung lớn nhất của các số \(v_1, v_2, \ldots, v_n\).

Nếu bạn thành công, bạn sẽ giúp Alice chứng minh rằng cô ấy xứng đáng với danh hiệu "Nữ hoàng toán học", và Bob sẽ phải chịu thua trong thử thách này!

Input

• Dòng đầu tiên chứa một số nguyên \(n\) \((1 \leq n \leq 10^5)\) --- độ dài của dãy số.
• Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, \ldots, a_n\) \((1 \leq a_i \leq 10^9)\) --- các phần tử trong dãy số.
• Dòng thứ ba chứa một số nguyên \(q\) \((1 \leq q \leq 3 \times 10^5)\) --- số lượng truy vấn.
• \(q\) dòng tiếp theo, mỗi dòng chứa một số nguyên \(x_i\) \((1 \leq x_i \leq 10^9)\) --- giá trị GCD mà Bob đang tìm kiếm.

Output

Với mỗi truy vấn, in ra số lượng cặp \((l, r)\) thỏa mãn yêu cầu trong một dòng riêng.

Example

3
2 6 3
5
1
2
3
4
6

1
2
2
0
1

Scoring

• Có \(25\%\) số test tương ứng với \(25\%\) số điểm có \(n, q \leq 100\).
• Có \(25\%\) số test tương ứng với \(25\%\) số điểm có \(n, q \leq 500\).
• Có \(25\%\) số test tương ứng với \(25\%\) số điểm có \(q \leq 3\).
• Có \(25\%\) số test tương ứng với \(25\%\) số điểm còn lại không có ràng buộc gì thêm.