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.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.StringTokenizer;
import java.util.Map;
import java.util.HashMap;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author ATailouloute
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        QuickScanner in = new QuickScanner(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        TaskD solver = new TaskD();
        solver.solve(1, in, out);
        out.close();
    }

    static class TaskD {
        public void solve(int testNumber, QuickScanner in, PrintWriter out) {
            LongCounter<Integer> cnt = new LongCounter<>();
            int n = in.nextInt();
            int[] a = in.nextIntArray(n);
            LongCounter<Integer> last = new LongCounter<>();
            for (int i = 0; i < n; i++) {
                LongCounter<Integer> cur = new LongCounter<>();
                for (int g : last.get().keySet()) {
                    cur.add(gcd(a[i], g), last.count(g));
                }
                cur.increment(a[i]);
                for (int g : cur.get().keySet()) {
                    cnt.add(g, cur.count(g));
                }
                last = cur;
            }
            int m = in.nextInt();
            for (int i = 0; i < m; i++) {
                int x = in.nextInt();
                out.println(cnt.count(x));
            }
        }

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

    }

    static class LongCounter<T> {
        Map<T, Long> data;
        long total;

        public LongCounter() {
            this.data = new HashMap<>();
        }

        public Long count(T key) {
            return data.containsKey(key) ? data.get(key) : 0L;
        }

        public void add(T key, long value) {
            set(key, count(key) + value);
            total += value;
        }

        public void increment(T key) {
            add(key, 1);
        }

        public Map<T, Long> get() {
            return data;
        }

        public void set(T key, Long value) {
            data.put(key, value);
        }

    }

    static class QuickScanner {
        BufferedReader br;
        StringTokenizer st;
        InputStream is;

        public QuickScanner(InputStream stream) {
            is = stream;
            br = new BufferedReader(new InputStreamReader(stream), 32768);
        }

        public String nextToken() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return st.nextToken();
        }

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

        public int[] nextIntArray(int len) {
            int[] a = new int[len];
            for (int i = 0; i < len; i++) {
                a[i] = nextInt();
            }
            return a;
        }

    }
}