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.HashMap;
import java.util.Map.Entry;
import java.util.StringTokenizer;
public class sparseTable {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter pw = new PrintWriter(System.out);
        StringTokenizer st = new StringTokenizer(br.readLine());
		int n=Integer.parseInt(st.nextToken());
		int a[]=new int[n];
		st=new StringTokenizer(br.readLine());
		for(int i=0;i<n;i++) {
			a[i]=Integer.parseInt(st.nextToken());
		}
		HashMap<Integer, Long> res=solve(n, a);
		st=new StringTokenizer(br.readLine());
		int q=Integer.parseInt(st.nextToken());
		for(int i=1;i<=q;i++) {
			st=new StringTokenizer(br.readLine());
			int gcd=Integer.parseInt(st.nextToken());
			pw.println(res.getOrDefault(gcd, (long) 0));
		}
		pw.close();
		
	}
	static HashMap<Integer, Long> solve(int n,int a[]) {
		HashMap<Integer, Long> res=new HashMap<>();
		HashMap<Integer, Long> divisors=new HashMap<>();
		HashMap<Integer, Long> nextDivisors=new HashMap<>();
		for(int i=0;i<n;i++) {
			for(Entry<Integer,Long> entry:divisors.entrySet()) {
				int num=entry.getKey();
				int gcd=gcd(a[i], num);
				nextDivisors.put(gcd, nextDivisors.getOrDefault(gcd, (long) 0)+entry.getValue());
			}
			nextDivisors.put(a[i], nextDivisors.getOrDefault(a[i], (long) 0)+1);
			for(Entry<Integer,Long> entry:nextDivisors.entrySet()) {
				res.put(entry.getKey(), res.getOrDefault(entry.getKey(), (long) 0)+entry.getValue());
			}
			divisors=nextDivisors;
			nextDivisors=new HashMap<>();
		}
		return res;
	}
	static int gcd(int a,int b) {
		if(b==0) {
			return a;
		}return gcd(b, a%b);
	}
	
}