题目描述

看到题目名字就知道这一定是一道数学题。没错，你猜对了，这就是一道数学题。 为了减少第一题大家的阅读时间，同时为了显示一下出题人的懒惰属性，这道题的题面就没有故事情节了。
问题描述如下：在课堂上，老师问完问题之后的静默是课堂尴尬的源泉，于是A同学想了一个简单的办法解决这一尴尬。A将所有的同学排成一排，每当老师问问题的时候，A同学便会随机一个区间的同学，学号为这个区间内所有的同学的学号的最大公约数的同学便要回答这个问题。提出方案之后同学们纷纷到A同学那里问自己有多大概率被随机到。A说只需要告诉有多少个区间的最大公约数等于这个同学的学号，他们自己就会算出概率。可是问的同学太多，只能请你帮忙求解一下了。

输入

第一行一个整数n表示这一列的同学数目
第二行n个整数 第i个整数表示第i名同学的学号
第三行一个整数q 表示询问的同学数量
接下来q行每行一个整数表示询问的同学学号

输出

q行，每行一个整数表示对应询问的同学的答案。

输入样例

4
10 20 5 15
3
5
10
1

输出样例

6
2
0

样例解释

区间【1,1】只有10一个数字 最大公约数为10
区间【1,2】有10，20两个数字，最大公约数为10
区间【1,3】有10,20,5,三个数字，最大公约数为5
区间【1,4】有10,20,5,15四个数字，最大公约数为5
区间【2,2】只有20一个数字，最大公约数为20
区间【2,3】有20,5,两个数字，最大公约数为5
区间【2,4】有20,5,15三个数字，最大公约数为5
区间【3,3】只有5一个数字，最大公约数为5
区间【3,4】有5,15两个数字，最大公约数为5
区间【4,4】只有15一个数字最大公约数为15

数据范围

30%的数据满足n<=100,q<=100
60%的数据满足 n<=1000,q<=1000
100%的数据满足 n<=10^5,q<=10^5 0<学号<10^9

限制

时间限制1秒,空间限制256M