给出一个长度为 $n$ $(1\le n\le 10^{5})$ 的序列和 $m$ $(1\le m\le 10^{5})$ 个询问。对于每个询问，输入 $x$ $(1\le x\le 10^{9})$，输出满足 $\gcd(a_l,a_{l+1},...,a_r)=x$ 的 $(i,j)$ 的对数。

第一行两个整数 $n,m$。 接下来的 $n$ 行，为序列，序列中的元素 $a_i$ 满足 $(1\le a_i \le 10^{9})$。 最后 $m$ 行，为询问。

输出 $m$ 行，每行一个整数，回答询问。

### Sample Explanation 1 与えられる数列は、問題文中のものです。