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.awt.List;
			    		import java.io.*;
			import java.math.BigInteger;
			import java.util.*;

			    		
			    		
			    		/*
			    		 * 
			    		 * daiict
			    		 *
			    		 * 
			    		 * 
			    		 */
			    		
			    		
			    		public class pprac {
			    			 FastScanner in;
			    			 PrintWriter out;
			    		
			    			static ArrayList[] adj;
			    			static ArrayList[] aadj;
			    		    static int last;
			    			static int n;
			    			static int m;
			    			
			    			static int[] dp1;
			    			static int[] dp2;
			    			static int color[];
			    			static int visited[];
			    			static long[] arr;
			    			static long[] brr;
			    			static double ans;
			    			static int array[];
			    			static int start[];
			    			static int finish[];
			    			static int pref[];
			    			static int tree[];
			    			static int maxval = 32;
			    		
			    			static int ttt[];
			    			static int sum = 0;
			    			static String s;
			    		
			    			static int cc = 0;
			    			static long min = Long.MAX_VALUE;
			    			
			    			static ArrayList<Integer> segt[];
			    			
			    		//for dfs do not delete
			    			static int dir[][] ={{1,0},{0,1},{0,-1},{-1,0}};
			    			
			    		
			    			static int[] seg;
			    			static long count = 1;
			    			static long mod = (long)1e9 + 7;
			    	
			    			static int parent[];
			    			static int size[];
			    			
			    		    static int[] l;
			    		    static int[] r;
			    		    static int[] next;
			    		    static int[] cnt;
			    		    static int[] block;
			    		    
			    		    static int bblock = 1001;
			    		    
			    			static HashSet<String> set;
			    			static HashSet<String> set2;
			    			
			    			static int low[];
			    			static int disc[];
			    			static int time;
			    			static int acn[];
			    			
			    			static HashMap<Long,Integer> map;
			    			
			    			static class Pair implements Comparable<Pair>
			    		    {
			    				int x;int y;int i;
			    				
			    		        Pair(int l, int m,int i) {
			    		          
			    		        	this.x = l;
			    		            this.y = m;
			    		            this.i = i;
			    		          
			    		        }
			    		        
			    		        public int compareTo(Pair p) {
			    		      
			    		        	
			    		            if (this.x/bblock == p.x/bblock) {
			    		                return (int)(this.y-p.y);
			    		            }
			    		            return (int)(this.x/bblock - p.x/bblock);
			    		        }
			    		        
			    		        public String toString(){
			    		        	return x + " " + y;
			    		        }
			    		        
			    		        public boolean equals(Object o){
			    		        	if(o instanceof Pair){
			    		        		Pair a = (Pair)o;
			    		        		
			    		        		return this.x == a.x;
			    		        	}
			    		        	
			    		        	return false;
			    		        }
			    		        
			    		        public int hashCode(){
			    		        	return new Long(x).hashCode()*31 + new Long(y).hashCode();
			    		        }
			    		    
			    		    }
			    		    
			    			
			    			public static int gcd(int a, int b) {
			    				if (b == 0) return a;
			    				return gcd(b, a%b);
			    			}
			    	
			    			void build(int n) {  // build the tree
			  				  for (int i = n - 1; i > 0; --i) seg[i] = Math.min(seg[i<<1],seg[i<<1|1]);
			  				}
		
			  			public static void modify(int p, int val,int n) {  // set value at position p
			  				  for (seg[p += n] = val; p > 1; p >>= 1) seg[p>>1] = Math.min(seg[p],seg[p^1]);
			  				}
		
			  				int query(int l, int r,int n) {  // sum on interval [l, r)
			  				  int res = Integer.MAX_VALUE;
			  				  
			  				  if(l>r){
			  					  return res;
			  				  }
			  				  
			  				  for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
			  				    if ((l&1) == 1) res = Math.min(res, seg[l++]);
			  				    if ((r&1) == 1) res = Math.min(res, seg[--r]);
			  				  }
			  				  return res;
			  				}
			    				
	//		    			public static void update(int x,int val){
	//		    				while(x<=maxval){
	//		    					tree[x] += val;
	//		    					x = (x&-x);
	//		    				}
	//		    			}
			    			
			    			public static int read(int idx){
			    				int sum = 0;
			    				
			    				while(idx>= 0){
			    					sum += tree[idx];
			    					idx -= (idx&(-idx));
			    				}
			    				
			    				return sum;
			    			}
			    			
			    			public static int find(int i){
			    				if(parent[i] != i){
			    					return find(parent[i]);
			    				}
			    				
			    				return i;
			    			}
			    			
			    			public static void union(int a,int b){
			    				int x = find(a);
			    				int y = find(b);
			    				
			    				if(x!=y){
			    					if(size[x] > size[y]){
			    						size[x] += size[y];
			    						parent[y] = x;
			    					}else{
			    						size[y] += size[x];
			    						parent[x] = y;
			    				}
			    				}
			    			}
			    			
			    			
			    			
			    			
			    			
			    		    /*static */ void solve() throws NumberFormatException,InputMismatchException, IOException {
			    		    
			    		 //   	Scanner in = new Scanner(System.in);
			    		    
			    		    	int n = in.nextInt();
			    		    	
			    		    	int arr[] = new int[n];
			    		    	
			    		    	for(int i = 0;i<n;i++){
			    		    		arr[i] = in.nextInt();
			    		    	}
			    		    	
			    		    	int q = in.nextInt();
			    		    	
			    		    	HashMap<Integer,Long> map = new HashMap();
			    		    	
			    		    	HashMap<Integer,Long> map2 = new HashMap();
			    		    	
			    		    	HashMap<Integer,Long> res = new HashMap();
			    		    	
			    		    	for(int i = 0;i<n;i++){
			    		    		map2.clear();
			    		    		
			    		    		for(Integer s:map.keySet()){
			    		    			int next = gcd(s,arr[i]);
			    		    			
			    		    			Long ss = map2.get(next);
			    		    			if(ss == null){
			    		    				map2.put(next, 0L);
			    		    			}
			    		    			
			    		    			map2.put(next, map2.get(next)+map.get(s));
			    		    			
			    		    		}
			    		    		map2.put(arr[i], (map2.get(arr[i]) == null)?1:map2.get(arr[i])+1);
			    		    		
			    		    		for(Integer s:map2.keySet()){
			    		    			long ss = map2.get(s);
			    		    			if(res.get(s) == null){
			    		    				res.put(s,0L);
			    		    			}
			    		    			res.put(s, res.get(s) + ss);
			    		    		}
			    		    		
			    		    		HashMap<Integer,Long> temp = map;
			    		    		map = map2;
			    		    		map2 = temp;
			    		    	}
			    		    
			    		    	
			    		    	for(int i = 0;i<q;i++){
			    		    		int x = in.nextInt();
			    		    		out.println((res.get(x) == null)?0:res.get(x));
			    		    	}
			    		    }
			    		    
			    			public static void remove(int i){
			    	    		if(disc[i] != 0){
			    	    			disc[i]--;
			    	    			low[disc[i]]--;
			    	    		}
			    	    	}
			    			
			    	    	public static void add(int i){
			    	    		low[disc[i]]++;
			    	    		disc[i]++;
			    	    	}
			    		    
			    		    
			    		    public static void uu(int arr[],int i,int f){
			    		    	if(i == 1){
			    		    		return;
			    		    	}
			    		    	int next = i/2;
			    		    	int x = 0;
			    		    	if(i%2 == 0){
			    		    		x = i+1;
			    		    	}else{
			    		    		x = i-1;
			    		    	}
			    		    	
			    		    	if(f == 1){
			    		    		arr[next] = arr[i] ^ arr[x];
			    		    	}else{
			    		    		arr[next] = arr[i]|arr[x];
			    		    	}
			    		    	
			    		    	uu(arr,next,1-f);
			    		    }
			    		    
			    		   
				    
			    		   
			    		  
			    		
			    		    public static String reverse(String s){
			    		    	
			    		    	String ans = "";
			    		    	
			    		    	for(int i = s.length()-1;i>=0;i--){
			    		    		ans += s.charAt(i);
			    		    	}
			    		    	
			    		    	return ans;
			    		    	
			    		    }
			    			
			    			
			    		    
			    		 
			    		    public static long sum(long x){
			    		    	return x<10?x:x%10 + sum(x/10);
			    		    }
			    			
			    			public static long gcd(long x, long y) {
			    				if (x == 0)
			    					return y;
			    				else
			    					return gcd( y % x,x);
			    			}
			    			static long inv(long x , long mod)
			    			{
			    				long r,y;
			    				for(r=1,y=mod-2;y!=0;x=x*x%mod,y>>=1)
			    				{
			    					if((y&1)==1)
			    						r=r*x%mod;
			    				
			    				}
			    				return r;
			    			}
			    			
			    			public static long pow(long x,long y,long n){
			    				if(y==0)
			    					return 1%n;
			    				if(y%2==0){
			    					long z=pow(x,y/2,n);
			    					return (z*z)%n;
			    				}
			    				return ((x%n)*pow(x,y-1,n))%n;
			    			}
			    			
			    			
			    			
			    			
			    			public static boolean isPrime(long a) {
			    				// Corner cases
			    				if (a <= 1)
			    					return false;
			    				if (a <= 3)
			    					return true;
			    		 
			    				// This is checked so that we can skip 
			    				// middle five numbers in below loop
			    				if (a % 2 == 0 || a % 3 == 0)
			    					return false;
			    		 
			    				for (long i = 5; i * i <= a; i = i + 6)
			    					if (a % i == 0 || a % (i + 2) == 0)
			    						return false;
			    		 
			    				return true;
			    			}
			    			
			    		
			    			void run() throws NumberFormatException, InputMismatchException,IOException {
			    				in = new FastScanner();
			    				out = new PrintWriter(System.out);
			    		
			    				solve();
			    		
			    				out.close();
			    			}
			    		
			    			class FastScanner {
			    				BufferedReader br;
			    				StringTokenizer st;
			    		
			    				public FastScanner() {
			    					br = new BufferedReader(new InputStreamReader(System.in));
			    				}
			    		
			    				String next() {
			    					while (st == null || !st.hasMoreTokens()) {
			    						try {
			    							st = new StringTokenizer(in.br.readLine());
			    						} catch (IOException e) {
			    							// TODO Auto-generated catch block
			    							e.printStackTrace();
			    						}
			    					}
			    					return st.nextToken();
			    				}
			    		
			    				int nextInt() {
			    					return Integer.parseInt(next());
			    				}
			    		
			    				long nextLong() {
			    					return Long.parseLong(next());
			    				}
			    		
			    				double nextDouble() {
			    					return Double.parseDouble(next());
			    				}
			    			}
			    			
			    			
			    			
			    			
			    		 
			    		
			    			public static void main(String[] args) throws NumberFormatException,InputMismatchException, IOException {
	//		    				 new Thread(null ,new Runnable(){
	//		    				       public void run(){
	//		    				           try{
	//		    				        		
	//		    				               test();
	//
	//		    				           } catch(Exception e){
	//		    				               e.printStackTrace();
	//		    				           }
	//		    				       }
	//		    				   },"1",1<<26).start();
	//		    				   	   }
	//		    				    static StringBuilder sb;
	//		    				    public static void test() throws IOException{
	//		    				    	 sb=new StringBuilder();
	//		    				    	int t=1;
	//		    				    	while(t-->0){
	//		    				    		
	//		    				    		solve();
	//		    				    		
	//		    				    	}
	//		    				    	
	
		    				    new pprac().run();
			    			}
			    				    
			    			
			    		}
			    		class Node{
			    			int a;
			    			int b;
			    			public Node(int i, int j) {
								this.a = i;
								this.b = j;
								
							}
						
			    			
			    		}
			    		
			    		class MyComp implements Comparator<String>{
			    		    
			    			int c = 0;
			    			
			    			MyComp(int d){
			    				c = d;
			    			}
			    			
			    			@Override
			    			public int compare(String a,String b) {
			    				
			    				// < == -1
			    				
			    				String arr[] = a.split(" ");
			    				String brr[] = b.split(" ");
			    				
			    				return arr[c].compareTo(brr[c]);
			    				
			    				
			    			}
			
			    			
			    		}
			    		
			    		class MyComp2 implements Comparator<Node>{
			    		    
			    		
			    			
			    			@Override
			    			public int compare(Node a,Node b) {
			    				
			    				// < == -1
			
			    				
			    				if(a.b > b.b){
			    					return -1;
			    				}else{
			    					return 1;
			    				}
			    				
			    				
			    			}
			
			    			
			    		}