SP1463 ROBOT - Robot Number M

著名的宇航员布鲁·玛丽终于把机器人一号送上了火星。 一号机器人非常聪明，每秒能造出一个机器人。 假设第一个机器人到达的时间是第二个1。在第二个i，机器人1号制造了一个新的机器人:机器人i号。(i > = 2) 新机器人一生产成功就开始工作了。机器人M只在第t秒休息，其中t是M的倍数。 例如，3号机器人在第4、5、7、8秒工作……在第二节6、9、……当一个机器人在休息时，他可以把自己的信息发送给新生产的机器人。 例如，当6号机器人成功生产时，2号机器人和3号机器人休息，所以6号机器人会从2号和3号机器人那里得到信息。 我们称机器人2号和3号是机器人6号的老师。如果两个机器人都不是另一个的老师，并且没有共同的老师，我们称它们为独立的。 请注意，1号机器人是独立于其他机器人的，不是其他机器人的老师，因为只有1号机器人可以制造机器人。 机器人M的生产量数量是在M之前生产出来的独立于M的机器人的数量。这里有一些例子: 机器人1号的数量为0； 2号机器人的数量为1；1号是它的生产者。 6号机器人的数量是2。1号和5号是生产者。 2号和3号是他的老师。 4号和他有一个共同的老师:2号。 机器人有三种职业。机器人No.M:如果M可以写成偶数个奇数素数的倍数，他就是个商人。 如果M可以写成奇数(包括1)的倍数，那么他就是一个黑客。 其他机器人都是医生。

第一行包含单个整数T，即测试用例的数量。 接下来的T组测试用例。 对于每个测试样例，第一行包含单个整数K。 下面是K行，每行包含两个整数：Pi和Ai 注意：M = P1^A1 * P2^A2 ...Pk^Ak

对于每组样例输入，输出三行，分别是商人、黑客、医生的数量（分别模1000取余）

Pi < 10000; 1