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 JAVA):

Solution:
import java.io.*;
import java.util.*;

public class Main{
    final boolean isFileIO = false; 
    BufferedReader in;
    PrintWriter out;
    StringTokenizer st = new StringTokenizer("");
    String delim = " ";

    public static void main(String[] args) throws IOException {
        Main m = new Main();
        m.initIO();
        m.solve();
        m.in.close();
        m.out.close();
    }

    public void initIO() throws IOException {
        if(!isFileIO) {
            in = new BufferedReader(new InputStreamReader(System.in));
            out = new PrintWriter(System.out);
        } else {
            in = new BufferedReader(new FileReader("input.txt"));
            out = new PrintWriter("output.txt"); 
        }
    }
  
    String nextToken() throws IOException {
        if(!st.hasMoreTokens()) {
            st = new StringTokenizer(in.readLine());
        }
        return st.nextToken(delim);
    }
 
    String readLine() throws IOException {
        return in.readLine();
    }

    int nextInt() throws IOException {
        return Integer.parseInt(nextToken());
    }

    long nextLong() throws IOException {
        return Long.parseLong(nextToken());
    }

    double nextDouble() throws IOException {
        return Double.parseDouble(nextToken());
    }

    int[][] table;
    int[] exp;
    int max = 18;
    public void solve() throws IOException {
        int n = nextInt();
        int[] a = new int[n];
        for(int i = 0; i < n; i++) {
            a[i] = nextInt();
        }
        table = new int[max][n];
        exp = new int[n + 1];
        for(int i = 1; i <= n; i++) {
            int p = 1;
            int j = 0;
            for(int k = 0; k < max; k++) {
                if((i & (1 << k)) == p) {
                    j = k;
                }
                p <<= 1;
            }
            exp[i] = j;
        }
        for(int i = 0; i < n; i++)
            table[0][i] = a[i];
        for(int i = 1; i < max; i++) {
            int pow = (1 << (i - 1));
            for(int j = 0; j < n; j++) {
                table[i][j] =  gcd(table[i - 1][j], table[i - 1][Math.min(j + pow, n - 1)]);
            }
        }
        HashMap<Integer, Long>  map= new HashMap<Integer, Long>();
        for(int i = 0; i < n; i++) {
            int r = n - 1;
            int left, right, mid, res, qu;
            while(r >= i) {
                left = i;
                right = r;
                res = query(left, right);
                while(left < right) {
                    mid = left + (right - left) / 2;
                    qu = query(i, mid);
                    if(qu > res) {
                        left = mid + 1;
                    } else {
                        right = mid;
                    }
                }
                Long cnt = map.get(res);
                if(cnt == null)
                    cnt = 0L;
                map.put(res, cnt + r - left + 1);
                r = left - 1;
            }
        }
        int q = nextInt();
        for(int i = 0; i < q; i++) {
            int x = nextInt();
            Long cnt = map.get(x);
            if(cnt == null)
                cnt = 0L;
            out.println(cnt);
        }
    }

    public int gcd(int a, int b) {
        if(b == 0)
            return a;
        return gcd(b, a % b);
    }

    int query(int l, int r) {
        int j = exp[r - l + 1];
        int pow = (1 << j);
        return gcd(table[j][l], table[j][l + r - (l + pow - 1)]);
    }
}