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.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.util.*;
import java.util.Map.Entry;
public class Solver {

	public static void main(String[] Args) throws NumberFormatException,
			IOException {
		new Solver().Run();
	}

	PrintWriter pw;
	StringTokenizer Stok;
	BufferedReader br;

	public String nextToken() throws IOException {
		while (Stok == null || !Stok.hasMoreTokens()) {
			Stok = new StringTokenizer(br.readLine());
		}
		return Stok.nextToken();
	}

	public int nextInt() throws NumberFormatException, IOException {
		return Integer.parseInt(nextToken());
	}

	public double nextDouble() throws NumberFormatException, IOException {
		return Double.parseDouble(nextToken());
	}

	public long nextLong() throws NumberFormatException, IOException {
		return Long.parseLong(nextToken());
	}

	long gcd(long a, long b){
		while (b>0){
			a=a%b;
			long buf=a;
			a=b;
			b=buf;
		}
		return a;
	}
	
	int n;
	long[] mas;
	Map<Long, Long> result=new TreeMap<Long, Long>();

	void addVal(Map<Long, Long> map, long val, long zn){
		Long kol=map.get(val);
		if (kol==null)
			kol=0L;
		kol+=zn;
		map.put(val, kol);
	}
	
	long getVal(Map<Long, Long> map, long val){
		Long kol=map.get(val);
		if (kol==null)
			kol=0L;
		return kol;
	}
	
	private void calcResult() {
		addVal(result, mas[0],1);
		Map<Long, Long> numbs=new TreeMap<Long, Long>();
		addVal(numbs, mas[0],1);
		for (int i=1; i<n; i++){
			Map<Long, Long> nextNumbs=new TreeMap<Long, Long>();
			addVal(nextNumbs, mas[i],1);
			addVal(result, mas[i], 1);
			for (Entry<Long, Long> zn : numbs.entrySet()){
				long next=gcd(zn.getKey(), mas[i]);
				addVal(result,next,zn.getValue());
				addVal(nextNumbs,next,zn.getValue());
			}
			numbs=nextNumbs;
		}
	}

	
	public void Run() throws NumberFormatException, IOException {
		//br = new BufferedReader(new FileReader("input.txt")); pw = new PrintWriter("output.txt");
		br=new BufferedReader(new InputStreamReader(System.in));  pw=new PrintWriter(new OutputStreamWriter(System.out));

//		PrintWriter in=new PrintWriter("input.txt");
//		in.println(100000);
//		Random rn=new Random();
//		for (int i=0; i<100000; i++){
//			in.print(rn.nextInt((int)1e9)+1);
//			in.print(' ');
//		}
//		in.println();
//		in.println(300000);
//		for (int i=0; i<300000; i++){
//			in.println(rn.nextInt((int)1e9)+1);
//		}
//		in.flush();
//		in.close();
		
//		long time=System.currentTimeMillis();
		n=nextInt();
		mas=new long[n];
		for (int i=0; i<n; i++){
			mas[i]=nextLong();
		}
		calcResult();
		int kol=nextInt();
		for (int i=0; i<kol; i++){
			long zn=nextLong();
			pw.println(getVal(result,zn));
		}
//		System.out.println(System.currentTimeMillis()-time);
		pw.flush();
		pw.close();
	}

	
}