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.*;
 
 
 
public class B {
	static int mod=1000_000_007;
	static int max;
	static int k;
	static int[] log;
	static int mat[][];
	public static void main(String[] args) throws Exception {
		PrintWriter out=new PrintWriter(System.out);
	    FastScanner fs=new FastScanner();
	    max=fs.nextInt();
	    
	    int arr[]=fs.readArray(max);
	    callog();
	    k=log[max];
	    mat=new int[max][k+1];
	    Map<Integer,Long> map=new HashMap<>();
	    build(arr);
	    for(int i=0;i<max;i++) {
	    	int id = i;
			while(id >= 0){
				int g=get_gcd(id,i);
				int tmp=bins(g,i);
				map.put(g, map.getOrDefault(g, (long)0)+(long)id-tmp+1);
				//ans[g] += (id-tmp+1);
				id=tmp-1;
			}
	    }
	    int q=fs.nextInt();
	    while(q-->0) {
	    	int ans=0;
	    	int x=fs.nextInt();
	    	if(map.containsKey(x))
	    	out.println(map.get(x));
	    	else out.println(0);
	    }
	    out.close();
	    
	}
	static int bins(int g,int top){
		int L=0,U=top,ans=0;
		while(L<=U){
			int m=(L+U)/2;
			if(get_gcd(m,top) >= g){
				ans = m;
				U = m-1;
			}
			else{
				L=m+1;
			}
		}
		return ans;
	}
	static int get_gcd(int l,int r) {
		int j=log[r-l+1];
		return gcd(mat[l][j], mat[r-(1<<j)+1][j]);
	}
	static int gcd(int a,int b) {
		if(b==0) return a;
		return gcd(b,a%b);
	}
	static void build(int arr[]) {
		for(int i=0;i<arr.length;i++) {
			mat[i][0]=arr[i];
		}
		for(int j=1;j<=k;j++) {
			for(int i=0;i+(1<<j)<=max;i++) {
				mat[i][j]=gcd(mat[i][j-1], mat[i+(1<<(j-1))][j-1]);
			}
		}
	}
	static void callog() {
		log=new int[max+1];
		log[1]=0;
		for(int i=2;i<=max;i++) log[i]=log[i/2]+1;
	}
	static void sort(int[] a) {
		//suffle
		int n=a.length;
		Random r=new Random();
		for (int i=0; i<a.length; i++) {
			int oi=r.nextInt(n);
			int temp=a[i];
			a[i]=a[oi];
			a[oi]=temp;
		}
		
		//then sort
		Arrays.sort(a);
	}
	
	// Use this to input code since it is faster than a Scanner
	static class FastScanner {
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st=new StringTokenizer("");
		String next() {
			while (!st.hasMoreTokens())
				try {
					st=new StringTokenizer(br.readLine());
				} catch (IOException e) {
					e.printStackTrace();
				}
			return st.nextToken();
		}
		
		int nextInt() {
			return Integer.parseInt(next());
		}
		int[] readArray(int n) {
			int[] a=new int[n];
			for (int i=0; i<n; i++) a[i]=nextInt();
			return a;
		}
		long nextLong() {
			return Long.parseLong(next());
		}
	}
 
}