The Boss on Mars
Time Limit : 2000/1000ms (Java/Other) Memory Limit : 32768/32768K (Java/Other)
Total Submission(s) : 3 Accepted Submission(s) : 1
Problem Description
On Mars, there is a huge company called ACM (A huge Company on Mars), and it¡¯s owned by a younger boss.<br><br>Due to no moons around Mars, the employees can only get the salaries per-year. There are n employees in ACM, and it¡¯s time for them to get salaries from their boss. All employees are numbered from 1 to n. With the unknown reasons, if the employee¡¯s work number is k, he can get k^4 Mars dollars this year. So the employees working for the ACM are very rich.<br><br>Because the number of employees is so large that the boss of ACM must distribute too much money, he wants to fire the people whose work number is co-prime with n next year. Now the boss wants to know how much he will save after the dismissal.<br>
Input
The first line contains an integer T indicating the number of test cases. (1 ¡Ü T ¡Ü 1000) Each test case, there is only one integer n, indicating the number of employees in ACM. (1 ¡Ü n ¡Ü 10^8)<br>
Output
For each test case, output an integer indicating the money the boss can save. Because the answer is so large, please module the answer with 1,000,000,007.<br>
Sample Input
2<br>4<br>5<br>
Sample Output
82<br>354<br><div style='font-family:Times New Roman;font-size:14px;background-color:F4FBFF;border:#B7CBFF 1px dashed;padding:6px'><div style='font-family:Arial;font-weight:bold;color:#7CA9ED;border-bottom:#B7CBFF 1px dashed'><i>Hint</i></div><br>Case1: sum=1+3*3*3*3=82<br>Case2: sum=1+2*2*2*2+3*3*3*3+4*4*4*4=354<br></div><br><br>
Author
ZHANG, Chao
Source
2011 Asia Dalian Regional Contest