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 Number_Theory;
import java.io.*;
import java.util.*;

/**
 * BEGIN NO SAD
 * Blessed are those who suffer for doing what is right.
 * The kingdom of heaven belongs to them.
 * (Matthew 5:10-12)
 * @author Tran Anh Tai
 * @template for CP codes
 * END NO SAD
 */
public class GCDQueries {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        Task solver = new Task();
        solver.solve(in, out);
        out.close();
    }
    // main solver
    static class Task{
        int a[] = new int[100000];
        public void solve(InputReader in, PrintWriter out) {
            int n = in.nextInt();
            Map<Integer, Long> gcdCount = new HashMap<>();
            Map<Integer, Integer> curDivisor = new HashMap<>();
            Map<Integer, Integer> auDivisor = new HashMap<>();
            for (int i = 0; i < n; i++){
                a[i] = in.nextInt();
            }
            for (int i = 0; i < n; i++){
                auDivisor.clear();
                for (int div : curDivisor.keySet()){
                    int key = gcd(div, a[i]);
                    int val = auDivisor.getOrDefault(key, 0) + curDivisor.get(div);
                    auDivisor.put(key, val);
                }
                auDivisor.put(a[i], auDivisor.getOrDefault(a[i], 0) + 1);
                curDivisor = clone(auDivisor);
                for (int key : curDivisor.keySet()){
                    gcdCount.put(key, gcdCount.getOrDefault(key, (long)0) + curDivisor.get(key));
                }
            }
            int q = in.nextInt();
            for (int i = 0; i < q; i++){
                int x = in.nextInt();
                out.println(gcdCount.getOrDefault(x, (long)0));
            }
        }

        private Map<Integer, Integer> clone(Map<Integer, Integer> auDivisor) {
            HashMap<Integer, Integer> clone = new HashMap<>();
            for (int key : auDivisor.keySet()){
                clone.put(key, auDivisor.get(key));
            }
            return clone;
        }

        public int gcd(int a, int b){
            if (a == 0){
                return b;
            }
            else{
                return gcd(b % a, a);
            }
        }
    }
    static class Pair{
        public int x, y;
        public Pair(int x, int y){
            this.x = x;
            this.y = y;
        }
    }
    static class Point{
        public double x, y;
        public Point(double x, double y){
            this.x = x; this.y = y;
        }
        public static Line getBisect(Point A, Point B){
            double a = B.x - A.x;
            double b = B.y - A.y;
            double c = a * (A.x + B.x) / 2 + b * (A.y + B.y) / 2;
            return new Line(a, b, c);
        }
        public static Point center(Point A, Point B, Point C){
            Line lab = getBisect(A, B);
            Line lac = getBisect(A, C);
            Point intersect = Line.intersect(lab, lac);
            return intersect;
        }
    }
    static class Line{
        public double a, b, c;
        public Line(double a, double b, double c){
            this.a = a; this.b = b; this.c = c;
        }
        public static Point intersect(Line l1, Line l2){
            double D = l1.a * l2.b - l1.b * l2.a;
            double Dy = l1.a * l2.c - l2.a * l1.c;
            double Dx = l1.c * l2.b - l2.c * l1.b;
            return new Point(Dx / D, Dy / D);
        }
    }
    // fast input reader class;
    static class InputReader {
        BufferedReader br;
        StringTokenizer st;

        public InputReader(InputStream stream) {
            br = new BufferedReader(new InputStreamReader(stream));
        }

        public String nextToken() {
            while (st == null || !st.hasMoreTokens()) {
                String line = null;
                try {
                    line = br.readLine();
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
                if (line == null) {
                    return null;
                }
                st = new StringTokenizer(line);
            }
            return st.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(nextToken());
        }
        public long nextLong(){
            return Long.parseLong(nextToken());
        }
    }
}