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

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 * @author Vadim Semenov
 */
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 counter = in.nextInt();
        int[] from = new int[counter];
        int[] gcd = new int[counter];
        int top = 0;
        Map<Integer, Long> cnt = new HashMap<>();
        for (int i = 0; i < counter; ++i) {
            int a = in.nextInt();
            gcd[top] = a;
            from[top] = i;
            top++;
            int newTop = 0;
            for (int j = 0; j < top; ++j) {
                gcd[j] = gcd(a, gcd[j]);
                if (j == 0) {
                    from[0] = 0;
                    newTop++;
                } else if (gcd[j] != gcd[j - 1]){
                    gcd[newTop] = gcd[j];
                    from[newTop] = from[j];
                    newTop++;
                }
            }
            top = newTop;
            for (int j = 0; j < top; ++j) {
                Long count = cnt.get(gcd[j]);
                if (count == null) {
                    count = 0L;
                }
                count += (j == top - 1 ? i : (from[j + 1] - 1)) - from[j] + 1;
                cnt.put(gcd[j], count);
            }
        }
        int queries = in.nextInt();
        for (int i = 0; i < queries; ++i) {
            int g = in.nextInt();
            Long result = cnt.get(g);
            if (result == null) {
                result = 0L;
            }
            out.println(result);
        }
    }

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

class InputReader {
    private final BufferedReader reader;
    private StringTokenizer tokenizer;

    public InputReader(InputStream in) {
        reader = new BufferedReader(new InputStreamReader(in));
    }

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

    public String next() {
        while (tokenizer == null || !tokenizer.hasMoreTokens()) {
            tokenizer = new StringTokenizer(readLine());
        }
        return tokenizer.nextToken();
    }

    public String readLine() {
        String line = null;
        try {
            line = reader.readLine();
        } catch (IOException e) {
            e.printStackTrace();
        }
        return line;
    }
}