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 static java.lang.Math.*; 

import java.io.*; 
import java.util.*; 
import java.math.*;

public class Main {
	BufferedReader in; 
	PrintWriter out;
	StringTokenizer st; 

	String next() {
		while (st==null || !st.hasMoreTokens()) {
			try {
				st = new StringTokenizer(in.readLine());
			} catch (Exception e) {}
		}
		return st.nextToken(); 
	}

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

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

	double nextDouble() {
		return Double.parseDouble(next());
	}

	HashMap<Integer, Long> ans = new HashMap<Integer, Long>(); 
	HashMap<Integer, Long>[] mp = new HashMap[2];

	void add(int x, long f) {
		if (!ans.containsKey(x)) ans.put(x, f); else {
			ans.put(x, f + ans.get(x));
		}
	}

	int gcd(int a, int b) {
		if (b==0) return a; 
		return gcd(b, a%b);
	}
	public void run() throws Exception {
		in = new BufferedReader(new InputStreamReader(System.in));
		out = new PrintWriter(System.out);             
		
		for (int i=0; i<2; i++) mp[i] = new HashMap<Integer, Long>();
		int n = nextInt(); 
		int[] a = new int[n]; 
		for (int i=0; i<n; i++) a[i] = nextInt();
		int Q = nextInt(); 

		int[] q = new int[Q]; 
		for (int i=0; i<Q; i++) q[i] = nextInt(); 

		for (int i=0; i<n; i++) {
			if (i == 0) {
				mp[i & 1].put(a[0], 1L);
				add(a[0], 1L);
				continue; 
			}
			int c = i & 1; 
			int p = 1-c;
			mp[c].clear();
			mp[c].put(a[i], 1L);
			add(a[i], 1L);
			for (Map.Entry<Integer, Long> e : mp[p].entrySet()) {
				int d = gcd(e.getKey(), a[i]);
				if (!mp[c].containsKey(d)) mp[c].put(d, 0L);
				long cr = mp[c].get(d);
				mp[c].put(d, cr + e.getValue());
				add(d, e.getValue());
			}
		}

		for (int i=0; i<Q; i++) {
			if (!ans.containsKey(q[i]))out.println(0); else out.println(ans.get(q[i]));
		}
		out.close(); 
 	}
	
	public static void main(String[] args) throws Exception {
		new Main().run(); 
	}

}