新年快到了，南开信竞队的队员们从全国各地聚到了一起，共来了N个人。何老板按照一种奇特的算法把它们从1到N编号。
使得对于编号i的队员，如果编号j队员跟他是老队友，那么j一定满足下列两个条件：

1. 1<=j<i；
   
2. i和j之间存在一个>1的公约数；
   
   在聚会现场，何老板提了M个问题，形如：x号同学的老队友有几个？
   对于何老板的每个提问，请你做出回答。
   在诸位大神级的前辈面前，你要回答得又快又准。

第一行，两个整数N和M
接下来一行，M个空格间隔的整数，表示何老板的M个询问

一行，M个空格间隔的整数，依次对应每个问题的答案

对于30%的数据:1<=N,M<=1000
对于100%的数据:1<=N<=10000000   1<=M<=100000