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 SparseTable;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;

public class CGCDSSQ {
    public static void main(String[] args)throws IOException {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        int n=Integer.parseInt(br.readLine());
        String line[]=br.readLine().split(" ");
        int a[]=new int[n];
        for(int i=0;i<n;i++){
            a[i]=Integer.parseInt(line[i]);
        }
        int table[][]=getTable(a);
        HashMap<Integer,Long> map=new HashMap<>();
        preprocess(table,map);
        StringBuilder print=new StringBuilder();
//        System.out.println(map.toString());
        int q=Integer.parseInt(br.readLine());
        while(q--!=0){
            int v=Integer.parseInt(br.readLine());
            print.append(map.getOrDefault(v,0l)+"\n");
        }
        System.out.println(print.toString());
    }
    public static int gcd(int a,int b){
        if(b==0){
            return a;
        }
        return gcd(b,a%b);
    }
    public static int[][] getTable(int a[]){
        int n=a.length;
        int m=Integer.numberOfTrailingZeros(Integer.highestOneBit(n));
        int table[][]=new int[n][m+1];
        for(int i=0;i<n;i++){
            table[i][0]=a[i];
        }
        for(int k=1;k<=m;k++){
            for(int i=0;i<n;i++){
                int end=i+(1<<(k-1));
                if(end<n){
                    table[i][k]=gcd(table[i][k-1],table[end][k-1]);
                }
                else{
                    table[i][k]=table[i][k-1];
                }
            }
        }
        return table;
    }
    public static int query(int table[][],int l,int r){
        int len=r-l+1;
        int k=Integer.numberOfTrailingZeros(Integer.highestOneBit(len));
        int prev=r-(1<<k)+1;
        return gcd(table[l][k],table[prev][k]);
    }
    public static void preprocess(int table[][],HashMap<Integer,Long> map){
        int n=table.length;
        for(int i=0;i<n;i++){
            int curr=i;
            while(curr<n){
                int val=query(table,i,curr);
                int low=curr;
                int high=n-1;
                int ans=0;
                while(low<=high){
                    int mid=(low+high)/2;
                    int q=query(table,i,mid);
                    if(q==val){
                        ans=Math.max(ans,mid-curr+1);
                        low=mid+1;
                    }
                    else{
                        high=mid-1;
                    }
                }
                map.put(val,map.getOrDefault(val,0l)+ans);
                curr+=ans;
            }
        }
    }
}