该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Description

火锅店有 $n$ 包底料，第 $i$ 包底料的辣度为 $a_i$。

有 $q$ 位同学来点锅底。第 $j$ 位同学给出一个整数 $x_j$，他只愿意选择辣度 $a_i$ 与 $x_j$ 互质的底料，也就是：$\gcd(a_i,x_j)=1$。

请你对每位同学回答：有多少包底料符合他的要求？

同学们的问题很多，老板不想每次都翻完整个仓库。毕竟底料会累，老板也会。

Format

Input

第一行两个整数 $n,q(1 \le n,q \le 2 \times 10^5)$。

第二行 $n$ 个整数 $a_1,a_2,\dots,a_n(1 \le a_i \le 10^6)$。

接下来 $q$ 行，每行一个整数 $x_j(1 \le x_j \le 10^6)$，表示一次询问。

Output

对于每次询问，输出一行一个整数，表示满足 $\gcd(a_i,x_j)=1$ 的 $a_i$ 数量。

Samples

6 4
2 3 4 6 9 25
6
5
10
7

1
5
2
6

Note

样例说明：

对于 $x=6$，只有 $25$ 与 $6$ 互质，答案为 $1$。

对于 $x=5$，除 $25$ 外的五个数都与 $5$ 互质，答案为 $5$。

对于 $x=10$，$3$ 和 $9$ 与 $10$ 互质，答案为 $2$。

对于 $x=7$，所有数都与 $7$ 互质，答案为 $6$。