Angel Speedcell

Time Limit: 2000/1000MS (Java/Others) Memory Limit: 128000/64000KB (Java/Others)

Problem Description

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 

each other.

Input

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.

Output

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.

Sample Input

4
2
3
4
5

Sample Output

Case #1: 0 31
Case #2: 31 242
Case #3: 242 1054
Case #4: 1296 3124

Hint

In the second case,their are three waves of fireballs,so the damage value to Ronhou will be 

(1*(1-1)+1^1*(1-1)+1^2*(1-1)+1^3*(1-1)+1^4*(1-1))+(1*(2-1)+2^1*(2-1)+2^2*(2-1)+2^3*(2-1)+2^4*(2-1))=31,

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.

Source

Shoutmon

Manager

Information
Solved Number9
Submit Number27
Problem Tags
number theory
No tag edit access
温馨提示:AC后可以编辑标签哦. ^-^
Login
LoginCancel