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 PYTHON3):

Solution:
from sys import stdin
import math
from collections import defaultdict
input = stdin.readline

n = int(input())
arr = list(map(int, input().rstrip().split(" ")))
q = int(input())

d = defaultdict(lambda : 0)

current = defaultdict(lambda : 0)
# totalCount1 = 0
# count1 = 0

for i in range(n):
    newCurrent = defaultdict(lambda : 0)
    newCurrent[arr[i]] += 1
    for key, value in current.items():
        g = math.gcd(arr[i], key)
        if g > 1:
            newCurrent[g] += value
        
    for key, value in newCurrent.items():
        d[key] += value
    
    current = newCurrent

totalCombi = (n * (n + 1)) // 2

#print(d)
d[1] = totalCombi - sum(d.values()) + arr.count(1)

#print(d)
for _ in range(q):
    x = int(input())
    print(d[x])