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.*;
import java.util.*;
import java.math.*;
import java.awt.image.AreaAveragingScaleFilter;
import static java.lang.Math.*;
import java.lang.*;



public class Main {
    static FastScanner in;
    static PrintWriter out;
    public static void main(String[] args) throws FileNotFoundException {
        runIO(0);

        Task solver = new Task();
        solver.solve(1, in, out);
        out.close();
    }

    public static void runIO(int R) throws FileNotFoundException{
        if (R==1){
            in = new FastScanner(new File("input.txt"));
            out = new PrintWriter(new File("output.txt"));
        } else
        {
            in = new FastScanner(System.in);
            out = new PrintWriter(System.out);
        }
    }
}


class Task {
    final int N = 1000010;
    int n, k;
    int a[] = new int[N];

    int gcd(int a, int b){
        while (a>0 && b>0)
            if (a>b) a%=b; else b%=a;
        return a+b;
    }

    void inc(Map<Integer, Long> a, int pos, long val){
        long x=val;
        if (a.containsKey(pos)) x+=a.get(pos);
        a.remove(pos);
        a.put(pos, x);
    }

    public void solve(int testNumber, FastScanner in, PrintWriter out) {
     n = in.nextInt();
     for (int i=0; i<n; i++) a[i] = in.nextInt();

        Map<Integer, Long> next = new TreeMap<>();
        Map<Integer, Long> div = new TreeMap<>();
        Map<Integer, Long> res = new TreeMap<>();


        for (int i=0; i<n; i++){
         next.clear();
         for (Map.Entry<Integer, Long> q : div.entrySet()){
             long x=0;
             int val = gcd(q.getKey(), a[i]);

             inc(next, val, q.getValue());
         }
         inc(next, a[i], 1);
            Map<Integer, Long> buf;

         buf = next;
         next = div;
         div = buf;
            for (Map.Entry<Integer, Long> q : div.entrySet()) inc(res, q.getKey(), q.getValue());
     }
     int q = in.nextInt();
     while (q-->0){
         int test = in.nextInt();
         if (res.containsKey(test)) out.println(res.get(test)); else out.println(0);
     }
    }
}

class FastScanner {
    BufferedReader br;
    StringTokenizer st;

    public FastScanner(File f) {
        try {
            br = new BufferedReader(new FileReader(f));
        } catch (FileNotFoundException e) {
            e.printStackTrace();
        }
    }

    public FastScanner(InputStream f) {
        br = new BufferedReader(new InputStreamReader(f));
    }

    String next() {
        while (st == null || !st.hasMoreTokens()) {
            String s = null;
            try {
                s = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            if (s == null)
                return null;
            st = new StringTokenizer(s);
        }
        return st.nextToken();
    }

    boolean hasMoreTokens() {
        while (st == null || !st.hasMoreTokens()) {
            String s = null;
            try {
                s = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            if (s == null)
                return false;
            st = new StringTokenizer(s);
        }
        return true;
    }

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

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

    double nextDouble() {
        return Double.parseDouble(next());
    }
}