Given a three-dimensional space of [1,n]×[1,n]×[1,n]. You're required to place some 1×1×1 cubes to make this 3D space look n×n square from above, from left and from front, while the plane xOy stand for the ground and z axis describes the height.
But placing these cubes must follow some restrictions. Obviously, it must obey the gravity laws. It means, when beneath a cube is empty, the height of this cube will drop one, until its height is exactly 1 (touch the ground) or there is another cube below it.
And besides that, placing cubes has some prices. If a cube is placed at an integer coordinate (x,y,z), the price will be x×y2×z.
Now, satisfying all the requirements above, you're required to calculate the minimum costs and the maximum costs.
Input
The first line contains an integer T(T≤15). Then T test cases follow.
For each test case, input a single integer n per line, while satisfying 1≤n≤1018.
Output
For each test case, output two lines. For the first line output the minimum costs mod 109+7. And for the second line, output the maximum costs mod 109+7.