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.util.*;
import java.io.*;
import java.math.*;
import java.awt.geom.*;

import static java.lang.Math.*;

public class Solution implements Runnable {
    
    int gcd(int a, int b) {
        while (b != 0) {
            a %= b;
            int temp = a;
            a = b;
            b = temp;
        }
        return a;
    }
    
    public void solve() throws Exception {
        int n = sc.nextInt();
        int logn = 0;
        while ((1 << logn) < n) {
            logn++;
        }
        
        int[][] sparseTable = new int[logn + 1][n];
        
        for (int i = 0; i < n; i++) {
            sparseTable[0][i] = sc.nextInt();
        }
        
        for (int it = 1; it <= logn; it++) {
            int step = (1 << it);
            int half = step >> 1;
            for (int i = 0; i + step <= n; i++) {
                sparseTable[it][i] = gcd(sparseTable[it - 1][i], sparseTable[it - 1][i + half]);
            }
        }
        
        HashMap<Integer, Long> result = new HashMap<Integer, Long>();
        
        for (int i = 0; i < n; i++) {
            int d = sparseTable[0][i];
            int l = i;
            while (l < n) {
                d = gcd(d, sparseTable[0][l]);
                int r = l;
                for (int it = logn; it >= 0; it--) {
                    if (r + (1 << it) > n) {
                        continue;
                    }
                    if (sparseTable[it][r] % d == 0) {
                        r += (1 << it);
                    }
                }
                if (!result.containsKey(d)) {
                    result.put(d, 0L);
                }
                result.put(d, result.get(d) + (r - l));
                l = r;
            }
        }
        
        int q = sc.nextInt();
        for (int i = 0; i < q; i++) {
            int x = sc.nextInt();
            if (!result.containsKey(x)) {
                out.println(0);
            } else {
                out.println(result.get(x));
            }
        }
    }

    static Throwable uncaught;

    BufferedReader in;
    FastScanner sc;
    PrintWriter out;

    @Override
    public void run() {
        try {
            in = new BufferedReader(new InputStreamReader(System.in));
            out = new PrintWriter(System.out);
            sc = new FastScanner(in);
            solve();
        } catch (Throwable uncaught) {
            Solution.uncaught = uncaught;
        } finally {
            out.close();
        }
    }

    public static void main(String[] args) throws Throwable {
        Thread thread = new Thread(null, new Solution(), "", (1 << 26));
        thread.start();
        thread.join();
        if (Solution.uncaught != null) {
            throw Solution.uncaught;
        }
    }

}

class FastScanner {

    BufferedReader in;
    StringTokenizer st;

    public FastScanner(BufferedReader in) {
        this.in = in;
    }

    public String nextToken() throws Exception {
        while (st == null || !st.hasMoreTokens()) {
            st = new StringTokenizer(in.readLine());
        }
        return st.nextToken();
    }

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

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

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

}