Miss DD is the most beautiful girl of NITJ. While working on her final year project, Miss DD found some interesting numbers known as CooCoo Numbers. The CooCoo numbers of order K are those numbers which have no. of prime divisors equal to K. Miss DD is facing a problem while handling them. She wants to know the count of all the CooCoo numbers of given order K which are less than or equal to N.
As she is not good in maths so she wants her boyfriend Divyank to solve this.
Input:
A number N will be given followed by Q the number of queries. Next Q lines will contain an integer K corresponding to the respective query.
Output:
Ouput the number of CooCoo numbers of order K which are less than or equal to N for each query.
Constraint:
2 ≤ N ≤ 1000000
1 ≤ K ≤ 10000000
1 ≤ Q ≤ 100000
First Query :
Order,k is 1 So the CooCoo numbers less than equal to 20 of order 1 are as follows
2 3 4 5 7 8 9 11 13 16 17 19
Because each one of them have only one prime divisor.
