Ronhou and Shoutmon trap in a maze which has many numbers on the ground.To their surprise,each number is a terrible trap.
If they step on a number n,there will be n waves of fireballs coming down from the sky,and hurt them.There are five fireballs in each
wave,and the original attack value of the five fireballs in the ith wave(1<=i<=n) is 1,i,i^2,i^3,i^4.However,the actual damage value of
each fireball will be the original attack value multiplied by (i-1) because of the fire property of the maze(so if it is the third wave,the
actual damage value of the five fireballs will be 2 , 6 , 18 , 54 , 162).Then,the final damage value will be the sum of all the fireballs.
Ronhou and Shoutmon are troubled by it,because they can’t escape from any one of the 5n fireballs without someone’s help.
But their is an angel named Speedcell in this maze.He loves Ronhou very much and a little love to Shoutmon.
The angel has two abilities:
Help people escape from all the fireballs in the ith wave if gcd(i,n)!=1.
Help people escape from all the fireballs in the ith wave if gcd(i,n)==1.
An ability can only be used to help one person.
Because Speedcell loves Ronhou more,so he will always use the first ability to Ronhou,and the second ability to Shoutmon.
Now,given a number n(2<=n<=10^9),please tell Speedcell that if he uses the two ability as long as he can,what is the final
damage value to Ronhou and Shoutmon.
Note:For each n,Ronhou will have 5n fireballs and Shoutmon will have the other 5n fireballs,and fireballs are independent with
The first line of input contains T (T≤1000),indicating the number of cases.Then T lines follow.Each line a integer n,indicating the
number they trap into.
Each case a line,and output the case number first,then two integers,the first integer indicates the final damage value to Ronhou,
and the second to Shoutmon.Please separate the two integers by a blank.The answer should be moduloed by 1000000007.
Case #1: 0 31
Case #2: 31 242
Case #3: 242 1054
Case #4: 1296 3124
In the second case,their are three waves of fireballs,so the damage value to Ronhou will be
and the damage value to Shoutmon will be 1*(3-1)+3*(3-1)+3^2*(3-1)+3^3*(3-1)+3^4*(3-1)=242.