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.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;

public class P152SUMD {

	public static void main(String[] args) throws IOException {
		initReader();
		int n = nextInt();

		HashMap<Integer, Long> result = new HashMap<>();
		List<Integer> gcd = new ArrayList<>();
		HashMap<Integer, Long> preCount = new HashMap<>();

		for (int i = 0; i < n; ++i) {
			int t = nextInt();
			HashMap<Integer, Long> curCount = new HashMap<>();
			List<Integer> cur = new ArrayList<>();
			for (Integer integer : gcd) {
				int m = gcd(integer, t);

				Long c = curCount.get(m);
				if (c == null) {
					c = 0l;
					cur.add(m);
				}

				curCount.put(m, c + preCount.get(integer));
			}
			Long c = curCount.get(t);
			if (c == null) {
				c = 0l;
				cur.add(t);
			}

			curCount.put(t, c + 1);
			for (Integer k : cur) {
				Long p = result.get(k);
				p = p == null ? 0 : p;
				p += curCount.get(k);
				result.put(k, p);
			}

			preCount = curCount;
			gcd = cur;
		}

		int q = nextInt();
		PrintWriter writer = new PrintWriter(System.out);
		for (int i = 0; i < q; ++i) {
			int t = nextInt();

			Long r = result.get(t);
			if (r == null) {
				writer.println(0);
			} else {
				writer.println(r);
			}
		}
		writer.close();

	}

	static int gcd(int a, int b) {
		return a % b == 0 ? b : gcd(b, a % b);
	}

	static BufferedReader reader;
	static StringTokenizer tokenizer;

	public static void initReader() {
		reader = new BufferedReader(new InputStreamReader(System.in));
		tokenizer = new StringTokenizer("");
	}

	static String next() throws IOException {
		while (!tokenizer.hasMoreTokens()) {

			tokenizer = new StringTokenizer(reader.readLine());

		}
		return tokenizer.nextToken();
	}

	static String nextLine() throws IOException {
		return reader.readLine();
	}

	static Integer nextInt() throws IOException {
		return Integer.parseInt(next());
	}

	static long nextLong() throws IOException {
		return Long.parseLong(next());
	}

	static Double nextDouble() throws IOException {
		return Double.parseDouble(next());
	}
}