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

/**
 * 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();
        long[] a = in.nextLongArr(n);
        HashMap<Long, Long> count = new HashMap<>();
        HashMap<Long, Long> cur = new HashMap<>();
        for (int i = 0; i < n; i++) {
            if (cur.containsKey(a[i])) {
                cur.put(a[i], cur.get(a[i]) + 1);
            } else {
                cur.put(a[i], 1L);
            }
            HashMap<Long, Long> next = new HashMap<>();
            for (long j : cur.keySet()) {
                long g = gcd(j, a[i]);
                if (next.containsKey(g)) {
                    next.put(g, next.get(g) + cur.get(j));
                } else {
                    next.put(g, cur.get(j));
                }
            }
            for (long j : next.keySet()) {
                if (count.containsKey(j)) {
                    count.put(j, count.get(j) + next.get(j));
                } else {
                    count.put(j, next.get(j));
                }
            }
            cur = next;
        }
        int q = in.nextInt();
        for (int i = 0; i < q; i++) {
            long x = in.nextLong();
            long ans = 0;
            if (count.containsKey(x))
                ans = count.get(x);

            out.println(ans);
        }
    }

    private long gcd(long a, long b) {
        return b == 0 ? a : gcd(b, a % b);
    }
}

class InputReader {
    public BufferedReader reader;
    public StringTokenizer tokenizer;

    public InputReader(InputStream stream) {
        reader = new BufferedReader(new InputStreamReader(stream), 32768);
        tokenizer = null;
        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());
    }

    public long nextLong() {
        return Long.parseLong(next());
    }

    public long[] nextLongArr(int n) {
        long[] arrs = new long[n];
        for (int i = 0; i < n; i++) {
            arrs[i] = nextLong();
        }
        return arrs;
    }

}