Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems.
×

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

D. CGCDSSQ

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputGiven a sequence of integers *a* _{1}, ..., *a* _{ n} and *q* queries *x* _{1}, ..., *x* _{ q} on it. For each query *x* _{ i} you have to count the number of pairs (*l*, *r*) such that 1 ≤ *l* ≤ *r* ≤ *n* and *gcd*(*a* _{ l}, *a* _{ l + 1}, ..., *a* _{ r}) = *x* _{ i}.

is a greatest common divisor of *v* _{1}, *v* _{2}, ..., *v* _{ n}, that is equal to a largest positive integer that divides all *v* _{ i}.

Input

The first line of the input contains integer *n*, (1 ≤ *n* ≤ 10^{5}), denoting the length of the sequence. The next line contains *n* space separated integers *a* _{1}, ..., *a* _{ n}, (1 ≤ *a* _{ i} ≤ 10^{9}).

The third line of the input contains integer *q*, (1 ≤ *q* ≤ 3 × 10^{5}), denoting the number of queries. Then follows *q* lines, each contain an integer *x* _{ i}, (1 ≤ *x* _{ i} ≤ 10^{9}).

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

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jul/09/2020 02:36:50 (f3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|