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.IOException;
import java.io.InputStream;
import java.util.HashMap;
import java.util.Map;

public class CGCDSSQ {
    static int N;
    static int[] A;
    
    static int gcd(int a, int b) {
        return (b==0) ? a : gcd(b, a%b);
    }

    public static void main(String[] args) throws IOException {
        InputReader reader = new InputReader(System.in);
        N = reader.readInt();
        A = new int[N];
        for (int n=0; n<N; n++) {
            A[n] = reader.readInt();
        }
        Map<Integer,Long> all = new HashMap<Integer,Long>();
        Map<Integer,Long> left = new HashMap<Integer,Long>();
        for (int n=0; n<N; n++) {
            int value = A[n];
            Map<Integer,Long> newLeft = new HashMap<Integer,Long>();
            for (Map.Entry<Integer,Long> entry : left.entrySet()) {
                int number = entry.getKey();
                long count = entry.getValue();
                int gcd = gcd(number, value);
                add(newLeft, gcd, count);
                add(all, gcd, count);
            }
            add(all, value, 1);
            add(newLeft, value, 1);
            left = newLeft;
        }
        int Q = reader.readInt();
        StringBuilder output = new StringBuilder(10*Q);
        for (int q=0; q<Q; q++) {
            int x = reader.readInt();
            Long result = all.get(x);
            if (result == null) {
                result = 0L;
            }
            output.append(result).append("\n");
        }
        System.out.print(output);
    }

    static void add(Map<Integer,Long> map, int value, long diff) {
        Long count = map.get(value);
        if (count == null) {
            count = diff;
        } else {
            count += diff;
        }
        map.put(value, count);
    }


    static final class InputReader {
        private final InputStream stream;
        private final byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;

        public InputReader(InputStream stream) {
            this.stream = stream;
        }

        private int read() throws IOException {
            if (curChar >= numChars) {
                curChar = 0;
                numChars = stream.read(buf);
                if (numChars <= 0) {
                    return -1;
                }
            }
            return buf[curChar++];
        }

        public final int readInt() throws IOException {
            int c = read();
            while (isSpaceChar(c)) {
                c = read();
            }
            int res = 0;
            do {
                res *= 10;
                res += c - '0';
                c = read();
            } while (!isSpaceChar(c));
            return res;
        }

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