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.HashMap;

public class D {

    private static final boolean DEBUG = true;

    private final void solve(final InputReader in, final OutputWriter out) throws Exception {
        int n = in.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; ++i) {
            a[i] = in.nextInt();
        }
        int m = in.nextInt();
        int[] q = new int[m];
        for (int i = 0; i < m; ++i) {
            q[i] = in.nextInt();
        }

        long[] results = solveTest(n, a, m, q);

        for (long result : results) {
            out.writeln(result);
        }
    }

    private final long[] solveTest(final int n, final int[] a, final int m, final int[] q) {
        long[] results = new long[m];

        final int pow = 18;
        int[][] p = new int[n][pow];
        for (int i = 0; i < n; ++i) {
            p[i][0] = a[i];
        }

        for (int st = 1; st < pow; ++st) {
            final int len = 1 << (st - 1);
            final int len2 = 1 << st;
            for (int i = 0; i <= n - len2; ++i) {
                p[i][st] = gcd(p[i][st - 1], p[i + len][st - 1]);
            }
        }

        HashMap<Integer, Long> computedResuls = new HashMap<Integer, Long>();

        for (int i = 0; i < n; ++i) {

            int lastr = i;
            int r = i;
            int gcd = p[i][0];

            for (; ; ) {

                for (int st = pow - 1; st >= 0; --st) {
                    if (r + (1 << st) - 1 >= n) {
                        continue;
                    }
                    if (p[r][st] % gcd == 0) {
                        r += (1 << st) - 1;
                    }
                }

                Long count = (long) (r - lastr + 1);
                Long currentCount = computedResuls.get(gcd);
                if (currentCount == null) {
                    currentCount = count;
                } else {
                    currentCount += count;
                }
                computedResuls.put(gcd, currentCount);

                ++r;
                if (r >= n) {
                    break;
                }
                lastr = r;
                gcd = gcd(gcd, a[r]);
                if (gcd == 1) {
                    r = n - 1;
                    count = (long) (r - lastr + 1);
                    currentCount = computedResuls.get(gcd);
                    if (currentCount == null) {
                        currentCount = count;
                    } else {
                        currentCount += count;
                    }
                    computedResuls.put(gcd, currentCount);
                    break;
                }
            }
        }

        for (int i = 0; i < m; ++i) {
            Long value = computedResuls.get(q[i]);
            if (value != null) {
                results[i] = value.longValue();
            }
        }

        return results;
    }

    private final int gcd(int a, int b) {
        for (; a != 0 && b != 0; ) {
            if (a > b) {
                a %= b;
            } else {
                b %= a;
            }
        }
        return a + b;
    }

    public static void main(String[] args) {

        try {

            final InputReader in;
            final OutputWriter out;

            if (!Boolean.parseBoolean(System.getProperty("ONLINE_JUDGE", "false"))) {

                final String fileIn = D.class.getSimpleName().toLowerCase() + ".in";
                final String fileOut = D.class.getSimpleName().toLowerCase() + ".out";

                in = new InputReader(new FileInputStream(fileIn));
                out = new OutputWriter(new FileWriter(fileOut));
            } else {

                in = new InputReader(System.in);
                out = new OutputWriter(new OutputStreamWriter(System.out));
            }

            new D().solve(in, out);

            out.close();

        } catch (Exception ex) {

            throw new RuntimeException(ex);
        }
    }

    private static final class InputReader {

        private static final byte ZERO = '0';
        private static final byte NINE = '9';

        private static final int BUFFER_SIZE = 1 << 20;

        private final BufferedInputStream in;

        private final byte[] buffer = new byte[BUFFER_SIZE];
        private int bufferSize = 0;
        private int offset = buffer.length;
        private final StringBuilder sb = new StringBuilder(1 << 20);

        private InputReader(final InputStream in) {
            this.in = (in instanceof BufferedInputStream) ? ((BufferedInputStream) in) : (new BufferedInputStream(in));
        }

        private final int read() throws Exception {
            if (offset >= bufferSize) {
                bufferSize = in.read(buffer);
                if (bufferSize <= 0) {
                    return -1;
                }
                offset = 0;
            }
            return buffer[offset++];
        }

        private final boolean isWhiteSpace(final int c) {
            return c == ' ' || c == '\r' || c == '\t' || c == '\n' || c == -1;
        }

        public final String next() throws Exception {
            sb.setLength(0);
            int c = read();
            while (isWhiteSpace(c)) {
                c = read();
            }
            while (!isWhiteSpace(c)) {
                sb.append((char) c);
                c = read();
            }
            return sb.toString();
        }

        public final int nextInt() throws Exception {
            int result = 0;
            boolean negative = false;
            int c = read();
            while (isWhiteSpace(c)) {
                c = read();
            }
            if (c == '-') {
                negative = true;
                c = read();
            }
            while (!isWhiteSpace(c)) {
                result = result * 10 - '0' + c;
                c = read();
            }
            return negative ? -result : result;
        }

        public final long nextLong() throws Exception {
            long result = 0;
            boolean negative = false;
            int c = read();
            while (isWhiteSpace(c)) {
                c = read();
            }
            if (c == '-') {
                negative = true;
                c = read();
            }
            while (!isWhiteSpace(c)) {
                result = result * 10 - '0' + c;
                c = read();
            }
            return negative ? -result : result;
        }
    }

    private static final class OutputWriter {

        private static final String NEW_LINE = String.format("%n");

        private final Writer output;
        private final StringBuilder buffer = new StringBuilder(1 << 20);

        public OutputWriter(final Writer output) {

            this.output = output;
        }

        public void write(final int i) {

            buffer.append(i);
        }

        public void write(final String s) {

            buffer.append(s);
        }

        public void writeln(final String s) {

            buffer.append(s);
            buffer.append(NEW_LINE);
        }

        public void writeln(final long l) {

            buffer.append(l);
            buffer.append(NEW_LINE);
        }

        public void writeln(final int i) {

            buffer.append(i);
            buffer.append(NEW_LINE);
        }

        public void close() throws Exception {

            output.write(buffer.toString());
            output.flush();
            output.close();
        }
    }
}