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;
template <typename T>
T Abs(T first) {
  return (first < 0 ? -first : first);
}
template <typename T>
T Sqr(T first) {
  return (first * first);
}
const int INF = (int)1e9;
const long double EPS = 1e-9;
const long double PI = acos(-1.0);
void Read(int &first) {
  char c, r = 0, n = 0;
  first = 0;
  for (;;) {
    c = getchar();
    if (c == '-')
      n = 1;
    else if ((c >= '0') && (c <= '9'))
      first = first * 10 + c - '0', r = 1;
    else if (r)
      break;
  }
  if (n) first = -first;
}
int gcd(int a, int b) { return (b ? gcd(b, a % b) : a); }
int main() {
  if (0) freopen("in.txt", "r", stdin);
  int N;
  int i, j, k, v, a;
  map<int, long long> M;
  static int V[100005], G[100005][20];
  Read(N);
  for (i = 0; i < N; i++) {
    Read(V[i]);
    G[i][0] = V[i];
  }
  for (i = N - 1; i >= 0; i--) {
    j = 0;
    while ((i + (1 << j) < N) && (G[i + (1 << j)][j])) {
      G[i][j + 1] = gcd(G[i][j], G[i + (1 << j)][j]);
      j++;
    }
  }
  for (i = 0; i < N; i++) {
    j = i;
    v = V[i];
    while (j < N) {
      if (i != j) v = gcd(v, V[j]);
      a = j + 1;
      for (k = 20 - 1; k >= 0; k--)
        if ((G[a][k]) && (G[a][k] % v == 0)) a += 1 << k;
      M[v] += a - j;
      j = a;
    }
  }
  Read(N);
  while (N--) {
    Read(i);
    cout << M[i] << endl;
  }
  return (0);
}