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.*;
import java.util.*;

public class cfBAYAND {
	static int[] maxpow;
	static int[][] st;
    public static void main(String[] args) throws Exception {
    	// BufferedReader in = new BufferedReader(new FileReader("cfBAYAND.in"));
    	BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    	
		int n = Integer.parseInt(in.readLine());
		String[] arr = in.readLine().split(" ");
		
		int mp = (int) (Math.log(n) / Math.log(2)) + 2;
		st = new int[mp][n];

		int[] a = new int[arr.length];
		for(int i = 0; i < a.length; i++) {
			a[i] = Integer.parseInt(arr[i]);
			st[0][i] = a[i];
		}
		
		for(int i = 1; (1 << i) <= n; i++) {
			for(int j = 0; j < n - (1 << i) + 1; j++) {
				st[i][j] = gcd(st[i - 1][j], st[i - 1][j + (1 << i - 1)]);
			}
		}

		maxpow = new int[n + 1];
		for(int i = 0; (1 << i) <= n; i++) {
			for(int j = (1 << i); j < (1 << i + 1) && j <= n; j++) {
				maxpow[j] = i;
			}
		}
		HashMap<Integer, Long> map = new HashMap<Integer, Long>();
		for(int i = 0; i < n; i++) {
			int curr = a[i];
			int ind = i;
			while(ind < n) {
				int min = ind;
				int max = n - 1;
				while(min < max) {
					int mid = min + max + 1 >> 1;
					int midi = q(i, mid);
					if(midi == curr) {
						min = mid;
					} else {
						max = mid - 1;
					}
				}
				if(map.containsKey(curr)) {
					map.put(curr, map.get(curr) + min - ind + 1);
				} else {
					map.put(curr, min - ind + 1L);
				}
				if(min + 1 < n) {
					curr = q(i, min + 1);
				}
				ind = min + 1;
			}
		}
		int q = Integer.parseInt(in.readLine());
		for(int i = 0; i < q; i++) {
			Long tmp = map.get(Integer.parseInt(in.readLine()));
			System.out.println(tmp == null ? 0 : tmp);
		}
	}

	public static int q(int l, int r) {
		int mp = maxpow[r - l + 1];
		return gcd(st[mp][l], st[mp][r - (1 << mp) + 1]);
	}

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