Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official.
×

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-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/18/2018 23:26:00 (d1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|