Chef recently took a course in linear algebra and learned about linear combinations of vectors. Therefore, in order to test his intelligence, Raj gave him a "fuzzy" problem to solve.
A sequence of integers $B_1, B_2, \ldots, B_M$ generates an integer $K$ if it is possible to find a sequence of integers $C_1, C_2, \ldots, C_M$ such that $C_1 \cdot B_1 + C_2 \cdot B_2 + \ldots + C_M \cdot B_M = K$.
In this problem, Chef has a sequence $A_1, A_2, \ldots, A_N$ and he should answer $Q$ queries. In each query, he is given an integer $K$; the answer to this query is the number of pairs $(l, r)$ such that $1 \le l \le r \le N$ and the subsequence $(A_l, A_{l+1}, \ldots, A_r)$ generates $K$.
Chef has no idea how to solve this problem ― can you help him find the answers to all queries?

-----Input-----
- The first line of the input contains a single integer $N$.
- The second line contains $N$ space-separated integers $A_1, A_2, \ldots, A_N$.
- The third line contains a single integer $Q$.
- The following $Q$ lines describe queries. Each of these lines contains a single integer $K$.

-----Output-----
For each query, print a single line containing one integer ― the number of contiguous subsequences that generate $K$.

-----Constraints-----
- $1 \le N, Q \le 10^5$
- $1 \le A_i \le 10^9$ for each valid $i$
- $1 \le K \le 10^6$

-----Subtasks-----
Subtask #1 (10 points): $1 \le N \le 1,000$
Subtask #2 (90 points): original constraints

-----Example Input-----
2
2 4
3
1
2
8

-----Example Output-----
0
2
3

-----Explanation-----
The sequence $(2, 4)$ has three contiguous subsequences: $(2)$, $(4)$ and $(2, 4)$. 
- In the first query, $1$ cannot be generated by any subsequence.
- In the second query, $2$ is generated by subsequences $(2)$ and $(2, 4)$. For example, for the subsequence $(2, 4)$, we can choose $C_1 = 1$ and $C_2 = 0$.
- In the third query, $8$ is generated by all three subsequences.

Difficulty: interview

Starter code:

Solutions:
import math
import bisect
from functools import reduce
from collections import defaultdict
# import sys
# input = sys.stdin.readline

def inn():
 return int(input())

def inl():
 return list(map(int, input().split()))

MOD = 10**9+7
INF = inf = 10**18+5

n = inn()
a = inl()
k = []
for q in range(inn()):
 k.append(inn())

gcdn = reduce(math.gcd, a)
lim = max(k)+1
ans = defaultdict(int)
ans[1] = 0

for i in range(n):
 cur_gcd = a[i]
 for j in range(i, n):
  cur_gcd = math.gcd(cur_gcd, a[j])
  if cur_gcd==1 or cur_gcd//gcdn==1:
   ans[cur_gcd] += (n-j)
   break
  ans[cur_gcd] += 1
# print(ans)

keys = list(ans.keys())
ans1 = [0]*lim
for i in keys:
 for j in range(i, lim, i):
  ans1[j] += ans[i]
# print(ans1[:10])
for i in k:
 print(ans1[i])

import math
import bisect
from functools import reduce
from collections import defaultdict
import sys
input = sys.stdin.readline

def inn():
 return int(input())

def inl():
 return list(map(int, input().split()))

MOD = 10**9+7
INF = inf = 10**18+5

n = inn()
a = inl()
k = []
for q in range(inn()):
 k.append(inn())

gcdn = reduce(math.gcd, a)
lim = max(k)+1
ans = defaultdict(int)
ans[1] = 0

for i in range(n):
 cur_gcd = a[i]
 for j in range(i, n):
  cur_gcd = math.gcd(cur_gcd, a[j])
  if cur_gcd==1 or cur_gcd//gcdn==1:
   ans[cur_gcd] += (n-j)
   break
  ans[cur_gcd] += 1
# print(ans)

keys = list(ans.keys())
ans1 = [0]*lim
for i in keys:
 for j in range(i, lim, i):
  ans1[j] += ans[i]
# print(ans1[:10])
for i in k:
 print(ans1[i])

import math
import bisect
from functools import reduce
from collections import defaultdict
import sys
input = sys.stdin.readline

def inn():
 return int(input())

def inl():
 return list(map(int, input().split()))

MOD = 10**9+7
INF = inf = 10**18+5

n = inn()
a = inl()
k = []
for q in range(inn()):
 k.append(inn())

gcdn = reduce(math.gcd, a)
lim = max(k)+1
ans = defaultdict(int)
ans[1] = 0

for i in range(n):
 cur_gcd = a[i]
 for j in range(i, n):
  cur_gcd = math.gcd(cur_gcd, a[j])
  if cur_gcd==1 or cur_gcd//gcdn==1:
   ans[cur_gcd] += (n-j)
   break
  ans[cur_gcd] += 1
# print(ans)

keys = list(ans.keys())
ans1 = [0]*lim
for i in keys:
 for j in range(i, lim, i):
  ans1[j] += ans[i]
# print(ans1[:10])
for i in k:
 print(ans1[i])

import math
import bisect
from functools import reduce
from collections import defaultdict

def inn():
 return int(input())

def inl():
 return list(map(int, input().split()))

MOD = 10**9+7
INF = inf = 10**18+5

n = inn()
a = inl()
k = []
for q in range(inn()):
 k.append(inn())

gcdn = reduce(math.gcd, a)
lim = max(k)+1
ans = defaultdict(int)
ans[1] = 0

for i in range(n):
 cur_gcd = a[i]
 for j in range(i, n):
  cur_gcd = math.gcd(cur_gcd, a[j])
  if cur_gcd==1 or cur_gcd//gcdn==1:
   ans[cur_gcd] += (n-j)
   break
  ans[cur_gcd] += 1
# print(ans)

keys = list(ans.keys())
ans1 = [0]*lim
for i in keys:
 for j in range(i, lim, i):
  ans1[j] += ans[i]
# print(ans1[:10])
for i in k:
 print(ans1[i])

import math
import bisect

def inn():
 return int(input())

def inl():
 return list(map(int, input().split()))

MOD = 10**9+7
INF = inf = 10**18+5

n = inn()
a = inl()
k = []
for q in range(inn()):
 k.append(inn())

lim = max(k)+1
ans = {}
is_gcd = [0]*lim
ans[1] = 0
for i in range(n):
 cur_gcd = a[i]
 for j in range(i, n):
  cur_gcd = math.gcd(cur_gcd, a[j])
  if cur_gcd==1:
   ans[1] += (n-j)
   break
  elif cur_gcd<lim:
   if is_gcd[cur_gcd]==0:
    is_gcd[cur_gcd] = 1
    ans[cur_gcd] = 0
   ans[cur_gcd] += 1
# print(ans)

keys = list(ans.keys())
ans1 = [0]*lim
for i in keys:
 for j in range(i, lim, i):
  ans1[j] += ans[i]
# print(ans1[:10])
for i in k:
 print(ans1[i])

from math import gcd
n=int(input())
it=list(map(int,input().split()))
q=int(input())
aa=[{} for i in range(n)]
aa[0][it[0]]=1
for i in range(1,n):
 
 for j in aa[i-1]:
  a=gcd(j,it[i])
  try:
   aa[i][a]+=aa[i-1][j]
  except:
   aa[i][a]=aa[i-1][j]
 try:
  aa[i][it[i]]+=1
 except:
  aa[i][it[i]]=1
ss={}
ma=10**6+1
k=-1
for i in aa:
 k+=1
 for j in i:
  if j>=ma:
   continue
  try:
   ss[j]+=aa[k][j]
  except:
   ss[j]=aa[k][j]
ll=list(ss.keys())
ll.sort()
pre=[0]*(10**6+1)
for i in ll:
 for j in range(i,len(pre),i):
  pre[j]+=ss[i]
for _ in range(q):
 k=int(input())
 print(pre[k])
 


from math import gcd
n=int(input())
it=list(map(int,input().split()))
q=int(input())
aa=[{} for i in range(n)]
aa[0][it[0]]=1
for i in range(1,n):
 
 for j in aa[i-1]:
  a=gcd(j,it[i])
  try:
   aa[i][a]+=aa[i-1][j]
  except:
   aa[i][a]=aa[i-1][j]
 try:
  aa[i][it[i]]+=1
 except:
  aa[i][it[i]]=1
ss={}
ma=10**6+1
k=-1
for i in aa:
 k+=1
 for j in i:
  if j>=ma:
   continue
  try:
   ss[j]+=aa[k][j]
  except:
   ss[j]=aa[k][j]
ll=list(ss.keys())
ll.sort()
pre=[0]*(10**6+1)
for i in ll:
 for j in range(i,len(pre),i):
  pre[j]+=ss[i]
for _ in range(q):
 k=int(input())
 print(pre[k])
 


"""
  Url: https://www.codechef.com/problems/FUZZYLIN
"""


__author__ = "Ronald Kaiser"
__email__ = "raios dot catodicos at gmail dot com"


from collections import defaultdict
from functools import reduce
from math import gcd


N = int(input())
A = list(map(int, input().split()))
Q = int(input())
K = [int(input()) for _ in range(Q)]
MAX_K = max(K)
D = defaultdict(int)
gcd_all = reduce(gcd, A)

for i in range(N):
 v = A[i]
 for j in range(i, N):
  v = gcd(v, A[j]) 
  if v == 1 or v//gcd_all == 1:
   D[v] += N - j 
   break
  D[v] += 1

s = D[1] if 1 in D else 0
T = [s for _ in range(MAX_K + 1)]

for k, v in list(D.items()):
 if k == 1: continue
 for i in range(k, MAX_K + 1, k):
  T[i] += v

for k in K: print(T[k])



# cook your dish here
"""
  Url: https://www.codechef.com/problems/FUZZYLIN
"""


__author__ = "Ronald Kaiser"
__email__ = "raios dot catodicos at gmail dot com"


from math import gcd
from collections import defaultdict


N = int(input())
A = list(map(int, input().split()))
Q = int(input())
K = [int(input()) for _ in range(Q)]

D = defaultdict(int)

t = A[0]
for i in range(1, N):
 t = gcd(t, A[i])

for i in range(N):
 v = A[i]
 for j in range(i, N):
  v = gcd(v, A[j]) 
  if v == 1:
   D[1] += N - j 
   break
  elif v//t == 1:
   D[v] += N - j
   break
  D[v] += 1

i = D[1] if 1 in D else 0
max_k = max(K)
T = [i for _ in range(max_k + 1)]

for k, v in list(D.items()):
 if k == 1:
  continue
 j = k
 x = 1
 while j <= max_k:
  T[j] += v
  x += 1
  j = k * x
#print(m, D, T)
for k in K:
 print(T[k])



import math
from collections import defaultdict
n=int(input())
a=[int(i) for i in input().split()]
q=int(input())
k=[int(input()) for i in range(q)]
K=max(k)
op=defaultdict(int)
gcd=defaultdict(int)
smallestgcd=a[0]
for i in a:
 gcd[i]+=1
 smallestgcd=math.gcd(smallestgcd,i)
s=[a[0]]

for i in range(1,n):
 for j in range(len(s)):
  if s[j]!=1 and s[j]!=smallestgcd:
   s[j]=math.gcd(a[i],s[j])
  gcd[s[j]]+=1
 s.append(a[i])
if gcd[1]!=0:
 op=defaultdict(lambda: gcd[1])
for i in gcd:
 j=i
 if j==1:
  continue
 while(j<K+1):
  op[j]+=gcd[i]
  j+=i
for z in range(q):
 print(op[k[z]])


import math
from collections import defaultdict
n=int(input())
a=[int(i) for i in input().split()]
q=int(input())
k=[int(input()) for i in range(q)]
K=max(k)
op=defaultdict(int)
gcd=defaultdict(int)
smallestgcd=a[0]
for i in a:
 gcd[i]+=1
 smallestgcd=math.gcd(smallestgcd,i)
s=[a[0]]

for i in range(1,n):
 for j in range(len(s)):
  if s[j]!=1 and s[j]!=smallestgcd:
   s[j]=math.gcd(a[i],s[j])
  gcd[s[j]]+=1
 s.append(a[i])
for i in gcd:
 j=i
 while(j<K+1):
  op[j]+=gcd[i]
  j+=i
for z in range(q):
 print(op[k[z]])


import math
from collections import defaultdict
n=int(input())
a=[int(i) for i in input().split()]
op=defaultdict(int)
gcd=defaultdict(int)
for i in a:
 gcd[i]+=1
s=[a[0]]
for i in range(1,n):
 for j in range(len(s)):
  s[j]=math.gcd(a[i],s[j])
  gcd[s[j]]+=1
 s.append(a[i])
for i in gcd:
 j=i
 while(j<10**6+1):
  op[j]+=gcd[i]
  j+=i
q=int(input())
for _ in range(q):
 print(op[int(input())])


import math
from collections import defaultdict
n=int(input())
a=[int(i) for i in input().split()]
op=defaultdict(int)
gcd=defaultdict(int)
for i in a:
 gcd[i]=1
while(len(a)!=0):
 newa=[]
 x=a[0]
 for i in a[1:]:
  z=math.gcd(x,i)
  gcd[z]+=1
  newa.append(z)
  x=i
 a=newa
for i in gcd:
 j=i
 while(j<10**6+1):
  op[j]+=gcd[i]
  j+=i
q=int(input())
for _ in range(q):
 print(op[int(input())])


import math
n=int(input())
a=[int(i) for i in input().split()]
op={}
gcd={}
for i in a:
 gcd[i]=1
while(len(a)!=0):
 newa=[]
 x=a[0]
 for i in a[1:]:
  z=math.gcd(x,i)
  try:
   gcd[z]+=1
  except:
   gcd[z]=1
  newa.append(z)
  x=i
 a=newa
for i in gcd:
 j=i
 while(j<10**6+1):
  try:
   op[j]+=gcd[i]
  except:
   op[j]=gcd[i]
  j+=i
q=int(input())
for _ in range(q):
 try:
  print(op[int(input())])
 except:
  print(0)


import math
n=int(input())
a=[int(i) for i in input().split()]
op=[0 for i in range(10**6+1)]
gcd={}
for i in a:
 gcd[i]=1
while(len(a)!=0):
 newa=[]
 x=a[0]
 for i in a[1:]:
  z=math.gcd(x,i)
  try:
   gcd[z]+=1
  except:
   gcd[z]=1
  newa.append(z)
  x=i
 a=newa
for i in gcd:
 j=i
 while(j<10**6+1):
  op[j]+=gcd[i]
  j+=i
q=int(input())
for _ in range(q):
 print(op[int(input())])


import math as mt
sz = 1000501
n = int(input())
x = [0]* sz
gcs = [0]* int(n)
a = [int(temp) for temp in input().split()]
gcs[n-1]=a[n-1]
i=n-2
while i>=0:
 gcs[i]=mt.gcd(gcs[i+1],a[i])
 i-=1
i=0
while i<n:
 curr = a[i]
 if curr < sz:
  x[curr] += 1
 j=i+1
 while j<n:
  curr = mt.gcd(curr,a[j])
  if curr ==gcs[j]:
   x[curr]+=(n-j)
   break
  elif curr<sz:
   x[curr]+=1
  j+=1
 i+=1
q = int(input())
for i in range (q):
 q1=int(input())
 ans = 0
 for t in range(1, int(mt.sqrt(q1)+1)):
  if q1%t ==0:
   if q1/t==t:
    ans += x[t]
   else:
    ans += x[t]
    ans += x[int(q1/t)]
 print(ans)


import math
import bisect

def inn():
 return int(input())

def inl():
 return list(map(int, input().split()))

MOD = 10**9+7
INF = inf = 10**18+5

n = inn()
a = inl()

ans = {}
is_gcd = [0]*1000001
ans[1] = 0
for i in range(n):
 cur_gcd = a[i]
 for j in range(i, n):
  cur_gcd = math.gcd(cur_gcd, a[j])
  if cur_gcd==1:
   ans[1] += (n-j)
   break
  elif cur_gcd<1000001:
   if is_gcd[cur_gcd]==0:
    is_gcd[cur_gcd] = 1
    ans[cur_gcd] = 0
   ans[cur_gcd] += 1
# print(ans)

keys = list(ans.keys())
ans1 = [0]*1000001
for i in keys:
 for j in range(i, 1000001, i):
  ans1[j] += ans[i]
# print(ans1[:10])

for q in range(inn()):
 k = inn()
 print(ans1[k])