#P16734. 波特筛
波特筛
题目描述
波特发明了一种筛法——波特筛!
可惜的是,由于时间过于久远,波特已经忘记了如何实现这种筛法。不过,它还记得波特筛能够解决的问题。
设正整数 的标准质因数分解为
其中 两两不同且均为质数, 为正整数。定义数论函数
特别地,空乘积为 ,因此 。
现在给定若干个 ,对于每次询问,你需要计算
输入格式
第一行包含一个整数 ,表示询问组数。
接下来 行,每行包含一个整数 ,表示一次询问。
输出格式
输出共 行。
对于每次询问,输出一行一个整数,表示
对 取模后的结果。
样例
5
1
10
1000
1000000
10000000000
1
89
91403
555853215
441242777
数据范围
- 对于 的数据,;
- 对于 的数据,;
- 对于 的数据,,;
- 对于全部数据,,。