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 N = 100010;
int a[N], b[3 * N];
map<int, long long> mp;
int c[N], d[N], nc, nd, cc[N], dd[N];
int gcd(int a, int b) {
  if (b)
    while (b ^= a ^= b ^= a %= b)
      ;
  return a;
}
void gao(int l, int r) {
  if (r - l <= 4) {
    for (int i = l; i <= r; i++) {
      int now = a[i];
      if (mp[now] != 0) mp[now]++;
      for (int j = i + 1; j <= r; j++) {
        now = gcd(now, a[j]);
        if (now == 1) {
          if (mp[1] != 0) {
            mp[1] += (r - j + 1);
            break;
          }
        }
        if (mp[now] != 0) mp[now]++;
      }
    }
    return;
  }
  int mi = (l + r) / 2;
  nc = nd = 0;
  int now = a[mi], t, k = mi;
  ;
  c[nc++] = now;
  for (int i = mi - 1; i >= l; i--) {
    t = gcd(now, a[i]);
    if (t != now) cc[nc - 1] = k - i, k = i, c[nc++] = t, now = t;
    if (now == 1) break;
  }
  cc[nc - 1] = k - l + 1;
  now = a[mi + 1];
  d[nd++] = now;
  k = mi + 1;
  for (int i = mi + 2; i <= r; i++) {
    t = gcd(now, a[i]);
    if (t != now) dd[nd - 1] = i - k, k = i, d[nd++] = t, now = t;
    if (now == 1) break;
  }
  dd[nd - 1] = r - k + 1;
  for (int i = 0; i < nc; i++) {
    for (int j = 0; j < nd; j++) {
      int y = gcd(c[i], d[j]);
      if (mp[y] != 0) mp[y] += (long long)cc[i] * dd[j];
    }
  }
  gao(l, mi), gao(mi + 1, r);
}
int main() {
  int n, m;
  scanf("%d", &n);
  for (int i = 0; i < n; i++) scanf("%d", &a[i]);
  scanf("%d", &m);
  for (int i = 0; i < m; i++) scanf("%d", &b[i]), mp[b[i]] = 1;
  gao(0, n - 1);
  for (int i = 0; i < m; i++) printf("%I64d\n", mp[b[i]] - 1);
  return 0;
}