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

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

class TaskD {
    public void solve(int testNumber, InputReader in, PrintWriter out) {
        int n = in.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; ++i)
            a[i] = in.nextInt();
        int[] log = new int[n + 1];
        for (int i = 1, j = 0; i <= n; ++i) {
            while (1 << (j + 1) <= i) ++j;
            log[i] = j;
        }
        int[][] gcd = new int[n][log[n] + 1];
        for (int i = 0; i < n; ++i)
            gcd[i][0] = a[i];
        for (int j = 1; 1 << j <= n; ++j) {
            for (int i = 0; i + (1 << j) <= n; ++i) {
                gcd[i][j] = gcd(gcd[i][j - 1], gcd[i + (1 << (j - 1))][j - 1]);
            }
        }
        Map<Integer, Long> count = new HashMap<>();
        for (int i = 0; i < n; ++i) {
            int last = i;
            int expect = 0;
            while (last < n) {
                expect = gcd(expect, a[last]);
                int low = last;
                int high = n - 1;
                while (low < high) {
                    int mid = (low + high + 1) / 2;
                    int k = log[mid - i + 1];
                    int partGCD = gcd(gcd[i][k], gcd[mid - (1 << k) + 1][k]);
                    if (partGCD == expect) low = mid;
                    else high = mid - 1;
                }
                int delta = low - last + 1;
                if (count.containsKey(expect)) {
                    count.put(expect, count.get(expect) + delta);
                } else {
                    count.put(expect, (long) delta);
                }
                last = low + 1;
            }
        }
        int numQueries = in.nextInt();
        for (int q = 0; q < numQueries; ++q) {
            int x = in.nextInt();
            Long answer = count.get(x);
            out.println(answer == null ? 0 : answer);
        }
    }

    private int gcd(int x, int y) {
        while (y != 0) {
            int t = x % y;
            x = y;
            y = t;
        }
        return x;
    }
}

class InputReader {
    private BufferedReader reader;
    private StringTokenizer tokenizer;

    public InputReader(InputStream stream) {
        reader = new BufferedReader(new InputStreamReader(stream), 32768);
        tokenizer = null;
    }

    public String next() {
        while (tokenizer == null || !tokenizer.hasMoreTokens())
            try {
                tokenizer = new StringTokenizer(reader.readLine());
            } catch (IOException e) {
                throw new RuntimeException(e);
            }
        return tokenizer.nextToken();
    }

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

}