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.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.HashMap;
import java.util.InputMismatchException;
import java.util.Map;
 
public class Main {
 
	static final long MOD = 1000000007;
 
	public static int gcd(int a, int b) {
		return (b == 0) ? a : gcd(b, a%b);
	}
	
	public static void main(String[] args) {
		InputReader in = new InputReader(System.in);
		PrintWriter out = new PrintWriter(System.out);
 
		int n = in.nextInt();
		
 
		int[] a = new int[n];
		for (int i = 0 ; i < n ; i++) {
			a[i] = in.nextInt();
		}
		int[][] gcd = new int[20][n];
		for (int i = 0 ; i < n ; i++) {
			gcd[0][i] = a[i];
		}
		for (int k = 1 ; k < 20 ; k++) {
			int len = 1<<(k-1);
			for (int i = 0 ; i < n ; i++) {
				if (i+len<n) {
					gcd[k][i] = gcd(gcd[k-1][i], gcd[k-1][i+len]);					
				} else {
					gcd[k][i] = gcd[k-1][i];
				}
			}
		}
		
		
		Map<Integer,Long> cnt = new HashMap<Integer,Long>();
		for (int i = 0 ; i < n ; i++) {
			int pl = i;
			int now = gcd[0][pl];
			while (pl < n) {
				int tpl = pl;
				now = gcd(now, gcd[0][tpl]);
				for (int k = 19 ; k >= 0 ; k--) {
					int len = 1<<k;
					if (tpl+len>n) {
						continue;
					}
					int tg = gcd(now, gcd[k][tpl]);
					if (tg == now) {
						tpl += len;
					}
				}
				int l = tpl - pl;
				if (!cnt.containsKey(now)) {
					cnt.put(now, 0L);
				}
				cnt.put(now, cnt.get(now)+l);
				pl = tpl;
			}
		}
		
		int m = in.nextInt();
		
		for (int i = 0 ; i < m ; i++) {
			int q = in.nextInt();
			if (!cnt.containsKey(q)) {
				out.println(0);
			} else {
				out.println(cnt.get(q));				
			}
		}
		out.flush();
	}
 
	static class InputReader {
		private InputStream stream;
		private byte[] buf = new byte[1024];
		private int curChar;
		private int numChars;
		private SpaceCharFilter filter;
 
		public InputReader(InputStream stream) {
			this.stream = stream;
		}
 
		public int next() {
			if (numChars==-1)
				throw new InputMismatchException();
			if (curChar>=numChars) {
				curChar = 0;
				try {
					numChars = stream.read(buf);
				} catch (IOException e) {
					throw new InputMismatchException();
				}
				if (numChars<=0)
					return -1;
			}
			return buf[curChar++];
		}
 
		public int nextInt() {
			int c = next();
			while (isSpaceChar(c))
				c = next();
			int sgn = 1;
			if (c=='-') {
				sgn = -1;
				c = next();
			}
			int res = 0;
			do {
				if (c<'0'||c>'9')
					throw new InputMismatchException();
				res *= 10;
				res += c-'0';
				c = next();
			} while (!isSpaceChar(c));
			return res*sgn;
		}
 
		public boolean isSpaceChar(int c) {
			if (filter!=null)
				return filter.isSpaceChar(c);
			return c==' '||c=='\n'||c=='\r'||c=='\t'||c==-1;
		}
 
		public interface SpaceCharFilter {
			public boolean isSpaceChar(int ch);
		}
	}
 
	public static void debug(Object... os) {
		System.err.println(Arrays.deepToString(os));
	}
}