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.util.*;
import java.io.*;
public class Solution{ 
static PrintWriter out = new PrintWriter(System.out);
static int gcd(int a,int b){
           if(b%a==0)
               return a;
               return gcd(b%a,a);
}
public static void main(String[] args) 
{ 
      int n = ni();
      int a[] = new int[n];
      for(int i=0;i<n;i++)
          a[i] = ni();
      HashMap<Integer,Long> ans = new HashMap();
      HashMap<Integer,Long> div = new HashMap();  // divisors
      HashMap<Integer,Long> ndiv = new HashMap(); // next divisor
      HashMap<Integer,Long> temp = new HashMap();

      for(int i=0;i<n;i++){
                  ndiv.clear();
               for(Map.Entry<Integer,Long> e : div.entrySet()){
                       int g = gcd(a[i],e.getKey());
                       long val = ndiv.getOrDefault(g,0l);
                       ndiv.put(g,val+e.getValue());
                }
                       ndiv.put(a[i],ndiv.getOrDefault(a[i],0l)+1);
                       temp =div; div =ndiv; ndiv=temp;
               for(Map.Entry<Integer,Long> e : div.entrySet()){
                       long val = ans.getOrDefault(e.getKey(),0l);
                       ans.put(e.getKey(),val+e.getValue());
                  }
      }
            int q = ni();
             for(int i=0;i<q;i++){
                 int x = ni();
                  out.println(ans.getOrDefault(x,0l));
             }
         out.flush();
}
 static FastReader sc=new FastReader(); 
 
      static int ni(){
                 int x = sc.nextInt();
                 return(x);
        }
      static long nl(){
              long x = sc.nextLong();
              return(x);
         }
      static String n(){
                 String str = sc.next();
                     return(str);
       }
     static String ns(){
                 String str = sc.nextLine();
                   return(str);
      }
     static double nd(){
               double d = sc.nextDouble();
                 return(d);
       }
  static class FastReader 
    { 
        BufferedReader br; 
        StringTokenizer st; 
  
        public FastReader() 
        { 
            br = new BufferedReader(new
                     InputStreamReader(System.in)); 
        } 
  
        String next() 
        { 
            while (st == null || !st.hasMoreElements()) 
            { 
                try
                { 
                    st = new StringTokenizer(br.readLine()); 
                } 
                catch (IOException  e) 
                { 
                    e.printStackTrace(); 
                } 
            } 
            return st.nextToken(); 
        } 
  
        int nextInt() 
        { 
            return Integer.parseInt(next()); 
        } 
  
        long nextLong() 
        { 
            return Long.parseLong(next()); 
        } 
  
        double nextDouble() 
        { 
            return Double.parseDouble(next()); 
        } 
  
        String nextLine() 
        { 
            String str = ""; 
            try
            { 
                str = br.readLine(); 
            } 
            catch (IOException e) 
            { 
                e.printStackTrace(); 
            } 
            return str; 
        } 
    } 
}