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

public class D {

	public D () {
		sc.nextInt();
		int [] A = sc.nextInts();

		XTreeMap<Integer> res = new XTreeMap<>();
		XTreeMap<Integer> Z = new XTreeMap<>();

		for (int a : A) {
			XTreeMap<Integer> Y = new XTreeMap<>();
			res.inc(a); Y.inc(a);
			for (int z : Z.keySet()) {
				int y = (int)gcd(z, a); long c = Z.get(z);
				Y.inc(y, c); res.inc(y, c);
			}
			Z = Y;
		}

		int Q = sc.nextInt();
		for (@SuppressWarnings("unused") int q : rep(Q)) {
			int x = sc.nextInt();
			long r = res.get(x);
			print(r);
		}
	}

	private static long gcd(long x, long y) { return BigInteger.valueOf(x).gcd(BigInteger.valueOf(y)).longValue(); }
	private static int [] rep(int N) { return rep(0, N); }
	private static int [] rep(int S, int T) { if (T <= S) return new int [0]; int [] res = new int [T-S]; for (int i = S; i < T; ++i) res[i-S] = i; return res; }
	private static abstract class XAbstractMap<K> implements Map<K, Long> {
		private final Map<K, Long> map;
		protected XAbstractMap(Map<K, Long> map) { this.map = map; }
		public void inc(K key) { inc(key, 1); }
		public void inc(K key, long value) { put(key, get(key) + value); }
		public long set(K key, long value) {
			long res = get(key);
			if (value != 0)
				map.put(key, value);
			else
				remove(key);
			return res;
		}
		///////////////////////////////////////////////////////////////////
		public int size() { return map.size(); }
		public boolean isEmpty() { return map.isEmpty(); }
		public boolean containsKey(Object key) { if (!isEmpty()) keySet().iterator().next().getClass().cast(key); return map.containsKey(key); }
		public boolean containsValue(Object value) { return map.containsValue(value); }
		public Long get(Object key) { return containsKey(key) ? map.get(key) : 0; }
		public Long put(K key, Long value) { return set(key, value); }
		public Long remove(Object key) { return map.remove(key); }
		public void putAll(Map<? extends K, ? extends Long> m) { map.putAll(m); }
		public void clear() { map.clear(); }
		public Set<K> keySet() { return map.keySet(); }
		public Collection<Long> values() { return map.values(); }
		public Set<java.util.Map.Entry<K, Long>> entrySet() { return map.entrySet(); }
	}
	private static class XTreeMap<K> extends XAbstractMap<K> { public XTreeMap() { super(new TreeMap<K, Long>()); } }
	////////////////////////////////////////////////////////////////////////////////////
	private final static IOUtils.MyScanner sc = new IOUtils.MyScanner();
	private static void print (Object o, Object ... A) { IOUtils.print(o, A); }
	private static class IOUtils {
		public static class MyScanner {
			public String next() { newLine(); return line[index++]; }
			public int nextInt() { return Integer.parseInt(next()); }
			public String nextLine() { line = null; return readLine(); }
			public String [] nextStrings() { return split(nextLine()); }
			public int [] nextInts() {
				String [] L = nextStrings();
				int [] res = new int [L.length];
				for (int i = 0; i < L.length; ++i)
					res[i] = Integer.parseInt(L[i]);
				return res;
			}
			//////////////////////////////////////////////
			private boolean eol() { return index == line.length; }
			private String readLine() {
				try {
					return r.readLine();
				} catch (Exception e) {
					throw new Error (e);
				}
			}
			private final java.io.BufferedReader r;
			private MyScanner () { this(new java.io.BufferedReader(new java.io.InputStreamReader(System.in))); }
			private MyScanner (java.io.BufferedReader r) {
				try {
					this.r = r;
					while (!r.ready())
						Thread.sleep(1);
					start();
				} catch (Exception e) {
					throw new Error(e);
				}
			}
			private String [] line;
			private int index;
			private void newLine() {
				if (line == null || eol()) {
					line = split(readLine());
					index = 0;
				}
			}
			private String [] split(String s) { return s.length() > 0 ? s.split(" ") : new String [0]; }
		}
		private static String build(Object o, Object ... A) { return buildDelim(" ", o, A); }
		private static String buildDelim(String delim, Object o, Object ... A) {
			StringBuilder b = new StringBuilder();
			append(b, o, delim);
			for (Object p : A)
				append(b, p, delim);
			return b.substring(delim.length());
		}
		//////////////////////////////////////////////////////////////////////////////////
		private static void start() { if (t == 0) t = millis(); }
		private static void append(StringBuilder b, Object o, String delim) {
			if (o.getClass().isArray()) {
				int len = java.lang.reflect.Array.getLength(o);
				for (int i = 0; i < len; ++i)
					append(b, java.lang.reflect.Array.get(o, i), delim);
			} else if (o instanceof Iterable<?>)
				for (Object p : (Iterable<?>) o)
					append(b, p, delim);
			else {
				if (o instanceof Double)
					o = new java.text.DecimalFormat("#.############").format(o);
				b.append(delim).append(o);
			}
		}
		private static java.io.PrintWriter pw = new java.io.PrintWriter(System.out);
		private static void print(Object o, Object ... A) { pw.println(build(o, A)); }
		private static void err(Object o, Object ... A) { System.err.println(build(o, A)); }
		private static void exit() {
			IOUtils.pw.close();
			System.out.flush();
			err("------------------");
			err(IOUtils.time());
			System.exit(0);
		}
		private static long t;
		private static long millis() { return System.currentTimeMillis(); }
		private static String time() { return "Time: " + (millis() - t) / 1000.0; }
	}
	public static void main (String[] args) { new D(); IOUtils.exit(); }
}