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:
//package e_contest_1;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.StringTokenizer;
import java.util.TreeMap;

public class CGCDSSQ {
	
	// static Range Minimum Query, DP Solution
	static class SparseTable {                                          
		  
		int A[], SpT[][];
		int log[];
		SparseTable(int[] A) 
		{
			int n = A.length;	this.A = A;
			int k = (int)Math.floor(Math.log(n) / Math.log(2)) + 1;
			SpT = new int[n][k];
			log = new int[A.length+1];
			
			for (int i = 0; i < n; i++) 
				SpT[i][0] = A[i]; 					// RMQ of sub array starting at index i and of length 2^0=1
		
			//overall time complexity = O(n log n)
			for (int j = 1; (1<<j) <= n; 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]);
		
			for(int i = 0;i<=n;i++) {
				log[i] = (int)Math.floor(Math.log(i)/Math.log(2));
			}
		}
		int gcd(int a, int b) {
			if(b==0)
				return a;
			return gcd(b, a%b);
			
		}
		  int query(int i, int j) 
		  {
			  
		    int k = log[j-i+1]; // 2^k <= (j-i+1)
		    return gcd(SpT[i][k],SpT[j-(1<<k)+1][k]);
		  } 
	}
	static int [] elm;
	static SparseTable sp;
	static int bsFarthest(int cur, int startClosest, int start) {
		int low = startClosest;
		int high =n-1;
		int ans = -1;
		while(low<=high) {
			int mid = (low+high)/2;
			int q = sp.query(start, mid);
			if(q>cur) {
				low = mid+1;
			}
			else if(q==cur) {
				ans = mid;
				low = mid+1;
			}else high = mid-1;
		}
		return ans;
	}
	static int n;
	static int bsClosest(int cur, int start) {
		int low = start;
		int high = n-1;
		int ans = -1;
		while(low<=high) {
			int mid = (low+high)/2;
			int q = sp.query(start, mid);
			if(q>cur) {
				low = mid+1;
			}
			else if(q==cur) {
				ans = mid;
				high = mid-1;
			}else high = mid-1;
		}
		return ans;
	}
	public static void main(String[] args) throws IOException{
		Scanner sc =new Scanner(System.in);
		 n = sc.nextInt();
		
		
		elm = new int[n];
		for(int i = 0; i <n; i++)
			elm[i] = sc.nextInt();
		sp =new SparseTable(elm);
//		System.out.println(3);
		int q = sc.nextInt();
		
		
		int [] queries =new int[q];
		for (int i = 0; i < queries.length; i++) {
			queries[i] =sc.nextInt();
		}
		long answers[] = new long[q];
		for (int i = 0; i < q; i++) {
			long counter = 0;
			
			answers[i]=counter;
		}
		TreeMap<Integer, Long> tm =new TreeMap<Integer,Long>();
		for (int i = 0; i < queries.length; i++) {
			tm.put(queries[i], 0l);
		}
		for (int j = 0; j < n; j++) {
			int gcd = elm[j];
			int startP = j;
			int far = bsFarthest(gcd,startP, j);
			if(tm.containsKey(gcd)) {
				long count = tm.get(gcd);
				tm.put(gcd, count+far-startP+1);
			}
			while(far!=n-1) {
				startP = far+1;
				gcd = sp.query(j, far+1);
				far = bsFarthest(gcd, startP, j);
				if(tm.containsKey(gcd)) {
					long count = tm.get(gcd);
					tm.put(gcd, count+far-startP+1);
				}
			}
			
		}
		PrintWriter out= new PrintWriter(System.out);
		for (int i = 0; i < queries.length; i++) {
			out.println(tm.get(queries[i]));
		}
		out.flush();
		out.close();
	}
	static class Scanner 
	{
		StringTokenizer st;
		BufferedReader br;

		public Scanner(InputStream s){	br = new BufferedReader(new InputStreamReader(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;
				}
			res += Long.parseLong(sb.toString()) / f;
			return res * (neg?-1:1);
		}
		
		public boolean ready() throws IOException {return br.ready();}


	}

}