给定一个整数序列 a1, ..., an 和 q 对其进行查询 x1, ..., xq 。对于每个查询 xi,您必须计算满足 1 ≤ l ≤ r ≤ n 且 gcd(al, al + 1, ..., ar) = xi 的对 (l, r) 的数量。
$$\gcd(v_{1},v_{2},\ldots,v_{n})$$ 是 v1, v2, ..., vn 的最大公约数,等于整除所有 vi 的最大正整数。
输入
输入的第一行包含整数n,(1 ≤ n ≤ 105),表示序列的长度。下一行包含 n 个空格分隔的整数 a1, ..., an, (1 ≤ ai ≤ 109)。
输入的第三行包含整数q,(1 ≤ q ≤ 3 × 105),表示查询的数量。接下来是 q 行,每行包含一个整数 xi,(1 ≤ xi ≤ 109)。
输出
对于每个查询,在单独的行中打印结果。
示例
输入 #1
3 2 6 3 5 1 2 3 4 6
输出 #1
1 2 2 0 1
输入 #2
7 10 20 3 15 1000 60 16 10 1 2 3 4 5 6 10 20 60 1000
输出 #2
14 0 2 2 2 0 2 2 1 1