F. Ramesses, Ra, and Roots
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Yan is on vacation in Egypt. But he doesn't forget his passion for mathematics. So, after hearing so many names in Egyptian history starting with the letter "R", like Ramesses and Ra, he remembers the following problem that involves taking roots of numbers.

Given $$$n$$$ integers $$$a_i$$$ and $$$q$$$ queries $$$r_i$$$, answer for each query how many of the $$$n$$$ integers are such that its $$$r_i$$$-th root is an integer.

Input

The first line contains 2 integers $$$n$$$ and $$$q$$$ ($$$1 \leq n,q \leq 10^5$$$). The second line contains $$$n$$$ integers $$$a_i$$$ ($$$1 \leq a_i \leq 10^9$$$). The third and last line contains $$$q$$$ integers $$$r_i$$$ ($$$1 \leq r_i \leq 10^9$$$), the queries.

Output

Print $$$q$$$ integers: the $$$i$$$-th must be the number of indices $$$j$$$ such that $$$a_j^{1/r_i}$$$ is an integer.

Example
Input
5 4
1 16 8 9 7
1 2 3 4
Output
5
3
2
2