#描述#
一天，小明上完数学课，知道了每个数都可以唯一地写成一个素因数相乘的形式。在吃饭的时候，他突然想到了这样一个数列。对于所有小于等于 N 的正整数，可以按数的素因子次方和来排列。例如，当N=8时，排列为：1 2 3 5 7 4 6 8<br>
也就是说，具有相同素因子次数和的数归为一类，排在后面的数的次数和一定大于排在前面的数的次数和。当次数和相等时，则按照从小到大排列。<br>
对于1，因为它本身是任何素数的0次方，所以它的素因子次数和为0。对于8，它可以写成2^3，故次方和为3。其间，有2,3,5,7，它们的次方和都为1，还有4,6它们的次方和都为2。所以，先按次方和从小到大排序，相同的次方和的整数中再按从小到大排序，得到上面的顺序1,2,3,5,7,4,6,8。<br>
显然对任何整数，所构成的次方和序，第一个数一定是1。<br>
现在对小明来说，最大的问题是对于给定的正整数N，如何快速找到其中小于N的某正整数P的排名。<br>

#格式#
##输入格式##
多组测试数据，不超过1000组。
每组数据有两行，第一行为N（N&lt=1000000），第二行包含不超过1000个正整数P（1&lt=P&lt=N），以-1结束。

##输出格式##
对于每个查询P，输出一行，给出 P在小于等于N的正整数中的排名。对于不同组查询之间应空一行。

#样例1#
##样例输入1##

8
3 5 6 8 -1
1
1 -1

##样例输出1##

3
4
7
8

1

#限制#
1000ms
32768KB

#提示#

#来源#
ycc