文理学院程序设计在线练习


小心超时

Time Limit: 1 Second(s)    Memory Limit: 32 MB

Total Submission(s): 121   Accepted Submission(s): 39
Problem Description

假设a为非负整数,N为正整数,我们定义
f(a, 1) = a
f(a, k) = f(a, k – 1) * f(a, k – 1) % N, k > 1
其中不一定存在正整数k满足f(a, k) = 0.你的任务就是,给定一个正整数N,找出有多少个a(0<= a <= N)是存在正整数k,满足f(a,k)=0。
你有把握在规定的时间解决这个问题吗?

Input

输入数据有多行,第一行是一个整数T,表示测试实例的个数,后面跟着T行,每行只包括一个正整数N(1<=N<=1000000000)

Output

每一行输出一个测试实例的结果。

Sample Input
6
2
12
50
180
245
361
Sample Output
2
3
6
7
8
20
Source

2008年绍兴市大学生计算机技能竞赛