AOJ 3431 - DIY Cube

DIY Cube

Time Limit: 2000ms

Memory Limit: 32768KB

This problem will be judged on HDU. Original ID: 3547
64-bit integer IO format: %I64d Java class name: Main

Submit Status Statistics

Font Size:

Description

Mr. D is interesting in combinatorial enumeration. Now he want to find out the number of ways on painting the vertexes of a cube. Suppose there are C different colors and two paintings are considered the same if they can transform from one to another by rotation.

Input

There are multiple test cases in the input, the first line of input contains an integer denoting the number of test cases.
For each test case, there are only one integer C, denoting the number of colors. (1 <= C <= 1000000000)

Output

For each test case, output the the number of painting ways. And if the number is equal or larger than 10¹⁵, output the last 15 digits.

Sample Input

Sample Output

Case 1: 1
Case 2: 23
Case 3: 031651434916928

Source

HyperHexagon's Summer Gift (Original tasks)