Problem: Given a sequence of integers a1, ..., an and q queries x1, ..., xq on it. For each query xi you have to count the number of pairs (l, r) such that 1 ≤ l ≤ r ≤ n and gcd(al, al + 1, ..., ar) = xi.

<image> is a greatest common divisor of v1, v2, ..., vn, that is equal to a largest positive integer that divides all vi.

Input

The first line of the input contains integer n, (1 ≤ n ≤ 105), denoting the length of the sequence. The next line contains n space separated integers a1, ..., an, (1 ≤ ai ≤ 109).

The third line of the input contains integer q, (1 ≤ q ≤ 3 × 105), denoting the number of queries. Then follows q lines, each contain an integer xi, (1 ≤ xi ≤ 109).

Output

For each query print the result in a separate line.

Examples

Input

3
2 6 3
5
1
2
3
4
6


Output

1
2
2
0
1


Input

7
10 20 3 15 1000 60 16
10
1
2
3
4
5
6
10
20
60
1000


Output

14
0
2
2
2
0
2
2
1
1

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
const int maxn = 300005;
const int ha = 19260817;
int gcd(int x, int y) { return y ? gcd(y, x % y) : x; }
struct hashmap {
  int hd[ha + 5], num[maxn], cnt, ne[maxn];
  long long sum[maxn];
  inline void clear() { cnt = 0; }
  inline void addpoint(int x) {
    int K = x % ha;
    for (int i = hd[K]; i; i = ne[i])
      if (num[i] == x) return;
    num[++cnt] = x, ne[cnt] = hd[K], hd[K] = cnt;
  }
  inline void add(int x, long long y) {
    int K = x % ha;
    for (int i = hd[K]; i; i = ne[i])
      if (num[i] == x) {
        sum[i] += y;
        return;
      }
  }
  inline long long query(int x) {
    int K = x % ha;
    for (int i = hd[K]; i; i = ne[i])
      if (num[i] == x) return sum[i];
    return 0;
  }
} M;
int n, a[maxn], X[maxn], m;
int L[233], T, R[233], S;
int pos[233], P[233];
inline int read() {
  int x = 0;
  char ch = getchar();
  for (; !isdigit(ch); ch = getchar())
    ;
  for (; isdigit(ch); ch = getchar()) x = x * 10 + ch - '0';
  return x;
}
inline void solve() {
  for (int i = 1; i <= n; i++) {
    L[++T] = a[i], P[T] = i, S = 0;
    for (int j = 1; j < T; j++) L[j] = gcd(L[j], a[i]);
    for (int j = 1; j <= T; j++)
      if (L[j] != L[j - 1]) R[++S] = L[j], pos[S] = P[j];
    for (int j = 1; j <= S; j++) L[j] = R[j], P[j] = pos[j];
    T = S;
    for (int j = 1; j < T; j++) M.add(L[j], P[j + 1] - P[j]);
    M.add(L[T], i + 1 - P[T]);
  }
}
int main() {
  M.clear(), n = read();
  for (int i = 1; i <= n; i++) a[i] = read();
  m = read();
  for (int i = 1; i <= m; i++) X[i] = read(), M.addpoint(X[i]);
  solve();
  for (int i = 1; i <= m; i++) printf("%I64d\n", M.query(X[i]));
  return 0;
}