jhljx选择狗带

题目描述

jhljx学了这么长时间C++，有一天突然发现一个奇怪的式子：jhljx=jh*ljx。这个式子或许存在这某种特殊的意义。对，特殊的意义就是乘法，所以jhljx爱上了阶乘，因为它有很多个数字相乘。
jhljx曾经在搞ACM的时候研究过几天的简单数论。发现一个简单的定理叫做唯一分解定理。也就是将一个整数写成几个素数的幂指数乘积的形式。

比如
$$12= 2^{2}\times3^{1}$$ $$100= 2^{2}\times5^{2}$$ $$360= 2^{3}\times3^{2}\times5^{1}$$ 而对于一个正整数n来说，$n!$除了可以写成 $$n!=1\times2\times3\times4(n-1)\times n$$ 之外，还可以写成
$$n!={x_1}^{p_{1}}\times{x_2}^{p_{2}}\ldots{x_t}^{p_{t}}$$ 其中${x_t}$为$1$~$n$的范围内最大的素数。

jhljx本想给你一个n，让你把n!转换为上述t个质数的幂指数的乘积形式。但是想到这个太难，你们会选择狗带。所以这个转换的任务留作思考题，请大家上机结束后自行编程实现。这个问题对于循环的考察很经典，也会在下次练习赛出现。

为了降低难度，jhljx给你了一个正整数$n$和一个小于等于$n$的正整数$m$，如果这个数字$m$为质数，那么求出在$n!$中$m$的幂指数。如果这个数字$m$不为质数，那么输出$I$ $choose$ $go$ $die$。

这个题的做法非常简单，首先判断m是否为质数。相信大家对于判断质数都已经会了。剩下的步骤只需循环即可求解。这样对于上述阶乘的唯一分解定理问题就可以在$O(n)$的时间内快速得到结果。

举个例子： 给一个数字n=10，m=2。 我们写出所有1~10中的数字，即
$1$ $2$ $3$ $4$ $5$ $6$ $7$ $8$ $9$ $10$
上面有5个数字满足条件，即$2$ $4$ $6$ $8$ $10$ 然后我们可以去掉这5个数字中的2，得到
$1$ $2$ $3$ $4$ $5$
上面有2个数字满足条件，即$2$ $4$ 然后我们可以去掉这两个数字中的2，得到
$1$ $2$
上面只有1个数字满足条件。即$2$ 这时，得到总数为8。
这个循环的操作过程充分利用了整数除法的特点，请你帮帮jhljx完成它吧。

输入

输入多组数据。 每组数据一行，为两个正整数n和m(1<=n<=1000000,1<=m<=n)

输出

如果这个数字$m$为质数，那么求出在$n!$中$m$的幂指数。如果这个数字$m$不为质数，那么输出$I$ $choose$ $go$ $die$。

输入样例

10 2
9 3
5 4

输出样例

8
4
I choose go die

jhljx温馨提示

还是整数除法的使用