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;
namespace Flandre_Scarlet {
int I() {
  char c = getchar();
  int x = 0;
  int f = 1;
  while (c < '0' or c > '9') f = (c == '-') ? -1 : 1, c = getchar();
  while (c >= '0' and c <= '9')
    x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();
  return (x = (f == 1) ? x : -x);
}
template <typename T>
void Rd(T& arg) {
  arg = I();
}
template <typename T, typename... Types>
void Rd(T& arg, Types&... args) {
  arg = I();
  Rd(args...);
}
void RA(int* p, int n) {
  for (int i = 1; i <= n; ++i) *p = I(), ++p;
}
int n, a[200005];
void Input() {
  n = I();
  RA(a + 1, n);
}
int st[200005][18];
short lg[200005];
inline int gcd(int a, int b) {
  while (b) {
    a ^= b ^= a ^= b;
    b %= a;
  }
  return a;
}
void SparseTable() {
  memset(lg, -1, sizeof(lg));
  for (int i = 0; i <= 17; ++i)
    if ((1 << i) <= n) lg[1 << i] = i;
  for (int i = 1; i <= n; ++i)
    if (lg[i] == -1) lg[i] = lg[i - 1];
  for (int i = 1; i <= n; ++i) st[i][0] = a[i];
  for (int j = 1; j <= 17; ++j) {
    for (int i = 1; i <= n; ++i)
      st[i][j] = gcd(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
  }
}
inline int Query(int l, int r) {
  int k = lg[r - l + 1];
  return gcd(st[l][k], st[r - (1 << k) + 1][k]);
}
unordered_map<int, long long> ans;
int GetNex(int l, int g) {
  if (Query(l, n) == g) return n + 1;
  int cur = l;
  for (int i = 17; i >= 0; --i)
    if (st[cur][i] % g == 0) cur = cur + (1 << i);
  return cur;
}
void Soviet() {
  SparseTable();
  for (int i = n; i >= 1; --i) {
    int g = a[i];
    for (register int l = i, r; l <= n; l = r) {
      r = GetNex(i, g);
      ans[g] += r - l;
      if (r == n + 1) break;
      g = gcd(g, a[r]);
    }
  }
  int q = I();
  for (int i = 1; i <= q; ++i) printf("%lld\n", ans[I()]);
}
void IsMyWife() {
  Input();
  Soviet();
}
}  // namespace Flandre_Scarlet
int main() {
  Flandre_Scarlet::IsMyWife();
  getchar();
  return 0;
}