409324: GYM103485 F Ramesses, Ra, and Roots

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.

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.

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

5 4
1 16 8 9 7
1 2 3 4

5
3
2
2