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.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.HashMap;
import java.util.StringTokenizer;


public class COVID {




static SparseTable st;
static HashMap<Integer,Long> cnt;
static int n;
public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);
		PrintWriter pw =new PrintWriter(System.out);
		 n= sc.nextInt();
		int[] arr= new int[n];
		for(int i=0;i<n;i++)arr[i]=sc.nextInt();
		 st= new SparseTable(arr);
		 cnt= new HashMap();
		
		for(int i=0;i<n;i++) {
			
			BS(i, i,i,n-1,arr[i]);
			
		}
		int q=sc.nextInt();
		for(int i=0;i<q;i++)
			pw.println(cnt.getOrDefault(sc.nextInt(), 0l));
		
		
		pw.flush();

}
		static void BS(int i,int start ,int lo , int hi, int val) {
			
			int l =lo,r=hi;
			while(lo<=hi) {
				int mid=lo+hi>>1;
				if( (st.query(i,mid))>=val) {
					lo=mid+1;
				}else {
					hi=mid-1;
				}
			}
		//	System.out.println(val+" "+hi+" "+start);
			cnt.put(val,cnt.getOrDefault(val, 0l)+hi-start+1);
			hi++;
			if(hi==n)return;
			BS(i,hi,hi,n-1,st.query(i, hi));
			
		}






static class SparseTable{
int[][] spt;
int n;
int k;
int[] log;
static int gcd(int a ,int b) {
	return (a==0)?b:gcd(b%a,a);
}

public SparseTable(int[] arr) {
	n=arr.length;
	
	k=(int)( Math.floor(Math.log(arr.length)/Math.log(2))+1);
	spt=new int[n][k];
	for(int i=0;i<n;i++)spt[i][0]=arr[i];
	
	for(int j=1;j<=k;j++)
		for(int i=0;i+(1<<j)-1<n;i++)
			spt[i][j]=gcd(spt[i][j-1],spt[i+(1<<(j-1))][j-1]);
	
	log=new int[n+1];
	for(int i=2;i<=n;i++)
		log[i]=log[i/2]+1;
}
public int query(int l , int r) {
	int k=log[r-l+1];
	return gcd(spt[l][k],spt[r-(1<<k)+1][k]);
}

}
static class Pair implements Comparable<Pair>{
	long  x;int y,z;
	public Pair(long a,int b, int c) {
		this.x=a;y=b;this.z=c;
	}


	public int compareTo(Pair o) {
		//return (this.x==o.x)?(this.y==o.y)?z-o.z:this.y-o.y:this.x-o.x;
		return this.x>o.x?1:(this.x<o.x)?-1:0;
	}

}




static class Scanner {
	StringTokenizer st;
	BufferedReader br;

	public Scanner(InputStream s) {
		br = new BufferedReader(new InputStreamReader(s));
	}
	public Scanner(String s) throws FileNotFoundException{	br = new BufferedReader(new FileReader(s));}


	public String next() throws IOException {
		while (st == null || !st.hasMoreTokens())
			st = new StringTokenizer(br.readLine()," ,");
		return st.nextToken();
	}

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

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

	public String nextLine() throws IOException {
		return br.readLine();
	}


	public double nextDouble() throws IOException {
		String x = next();
		StringBuilder sb = new StringBuilder("0");
		double res = 0, f = 1;
		boolean dec = false, neg = false;
		int start = 0;
		if (x.charAt(0) == '-') {
			neg = true;
			start++;
		}
		for (int i = start; i < x.length(); i++) {
			if (x.charAt(i) == '.') {
				res = Long.parseLong(sb.toString());
				sb = new StringBuilder("0");
				dec = true;
			} else {
				sb.append(x.charAt(i));
				if (dec)
					f *= 10;
			}
			if (sb.length() == 18) {
				res += Long.parseLong(sb.toString()) / f;
				sb = new StringBuilder("0");
			}
		}
		res += Long.parseLong(sb.toString()) / f;
		return res * (neg ? -1 : 1);
	}

	public boolean ready() throws IOException {
		return br.ready();
	}

}

public static void shuffle(int[] a) {
	int n = a.length;
	for (int i = 0; i < n; i++) {
		int r = i + (int) (Math.random() * (n - i));
		int tmp = a[i];
		a[i] = a[r];
		a[r] = tmp;
	}
}
}