Given 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}.

$\operatorname{gcd}(v_{1}, v_{2}, \ldots, v_{n})$ 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

Difficulty: interview

Starter code:

Solutions:
import sys
from collections import defaultdict
from math import gcd, sqrt

MAX = pow(10, 5)
# stdin = open("testdata.txt", "r")
ip = sys.stdin

n = int(ip.readline())

a = list(map(int, ip.readline().split()))
gcd_count = defaultdict(int)

main_gcd = defaultdict(int)

main_gcd[a[0]] = 1
gcd_count[a[0]] = 1
for i in range(1, n):
	ele = a[i]
	temp_gcd = defaultdict(int)
	temp_gcd[ele] = 1
	gcd_count[ele] += 1
	for k, v in main_gcd.items():
		temp = gcd(ele, k)
		temp_gcd[temp] += v
		gcd_count[temp] += v
	main_gcd = temp_gcd

q = int(ip.readline())
for _ in range(q):
	k = int(ip.readline())
	print(gcd_count[k])

from math import gcd
from collections import defaultdict
from sys import stdin, stdout

##This method is better cause for all the same results we only calculate once
def main():
    GCD_count = defaultdict(int)
    GCD_map = defaultdict(int)
    arr_len = int(stdin.readline())
    arr = [int(x) for x in stdin.readline().split()]
    for start in range(arr_len):
        temp = defaultdict(int)
        GCD_count[arr[start]] += 1
        temp[arr[start]] += 1
        for gcd_now, occurence in list(GCD_map.items()):
            res = gcd(gcd_now, arr[start])
            temp[res] += occurence
            GCD_count[res] += occurence
        GCD_map = temp
    num_queries = int(stdin.readline())
    for _ in range(num_queries):
        print(GCD_count[int(stdin.readline())])


main()


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])

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)

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)
        newCurrent[g] += value
        
    for key, value in newCurrent.items():
        d[key] += value
    
    current = newCurrent


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

from sys import stdin
n = int(stdin.readline())
a = [int(x) for x in stdin.readline().split()]

q = int(stdin.readline())

def gcd(a,b):
    while a != 0:
        a,b = b%a, a
    return b
    
totals = {}
new = {}

for x in a[::-1]:
    old = new
    new = {}
    for y in old:
        g = gcd(x,y)
        if g in new:
            new[g] += old[y]
        else:
            new[g] = old[y]
    if x in new:
        new[x] += 1
    else:
        new[x] = 1
    for y in new:
        if y in totals:
            totals[y] += new[y]
        else:
            totals[y] = new[y]
    
            


for x in range(q):
    c = int(stdin.readline())
    if c in totals:
        print(totals[c])
    else:
        print(0)


from sys import stdin
import math
from collections import defaultdict

input = stdin.readline

# n, k = map(int, input().split(" "))
# l = list(map(int, input().split(" ")))

n = int(input())
l = list(map(int, input().split(" ")))

k = math.ceil(math.log2(n))
dp = [[0] * k for i in range(2 ** k)]


def make_sparse(l, n, k):
    """Making sparse table, replace max with needed function like[GCD, Min, max, sum]"""
    for i in range(n):
        dp[i][0] = l[i]

    for j in range(1, k + 1):
        i = 0
        while i + (1 << j) <= n:
            dp[i][j] = math.gcd(dp[i][j - 1], dp[i + (1 << (j - 1))][j - 1])
            i += 1


def querys(l, r):
    j = int(math.log2(r - l + 1))
    return math.gcd(dp[l][j], dp[r - (1 << j) + 1][j])


make_sparse(l, n, k)
d = defaultdict(int)
g = defaultdict(int)
d[l[0]] = 1
g[l[0]] = 1
for i in range(1, n):
    t = defaultdict(int)
    t[l[i]] = 1
    g[l[i]]+=1
    for k, v in list(d.items()):
        gcd = math.gcd(k, l[i])
        t[gcd] += v
        g[gcd] += v
    d = t

for i in range(int(input())):
    a = g[int(input())]
    if not a:
        print(0)
    else:
        print(a)


from sys import stdin
import math
from collections import defaultdict

input = stdin.readline

# n, k = map(int, input().split(" "))
# l = list(map(int, input().split(" ")))

n = int(input())
l = list(map(int, input().split(" ")))

k = math.ceil(math.log2(n))
dp = [[0] * k for i in range(2 ** k)]


# def make_sparse(l, n, k):
#     """Making sparse table, replace max with needed function like[GCD, Min, max, sum]"""
#     for i in range(n):
#         dp[i][0] = l[i]
#
#     for j in range(1, k + 1):
#         i = 0
#         while i + (1 << j) <= n:
#             dp[i][j] = math.gcd(dp[i][j - 1], dp[i + (1 << (j - 1))][j - 1])
#             i += 1
#
#
# def querys(l, r):
#     j = int(math.log2(r - l + 1))
#     return math.gcd(dp[l][j], dp[r - (1 << j) + 1][j])


# make_sparse(l, n, k)
d = defaultdict(int)
g = defaultdict(int)
d[l[0]] = 1
g[l[0]] = 1
for i in range(1, n):
    t = defaultdict(int)
    t[l[i]] = 1
    g[l[i]]+=1
    for k, v in list(d.items()):
        gcd = math.gcd(k, l[i])
        t[gcd] += v
        g[gcd] += v
    d = t

for i in range(int(input())):
    a = g[int(input())]
    if not a:
        print(0)
    else:
        print(a)


from sys import stdin
import math
from collections import defaultdict

input = stdin.readline

# n, k = map(int, input().split(" "))
# l = list(map(int, input().split(" ")))

n = int(input())
l = list(map(int, input().split(" ")))


d = defaultdict(int)
g = defaultdict(int)
d[l[0]] = 1
g[l[0]] = 1
for i in range(1, n):
    t = defaultdict(int)
    t[l[i]] = 1
    g[l[i]]+=1
    for k, v in list(d.items()):
        gcd = math.gcd(k, l[i])
        t[gcd] += v
        g[gcd] += v
    d = t

for i in range(int(input())):
    a = g[int(input())]
    print(a)