Bayan 2015 Contest Warm Up |
---|

Finished |

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.

brute force

data structures

math

*2000

No tag edit access

The problem statement has recently been changed. View the changes.

×
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-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jun/09/2023 04:16:17 (k3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|