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\times y^2\times z$.

Now, satisfying all the requirements above, you're required to calculate the minimum costs and the maximum costs.

The first line contains an integer $T$($T\le 15$). Then $T$ test cases follow.

For each test case, input a single integer $n$ per line, while satisfying $1\le n\le10^{18}$.

For each test case, output two lines. For the first line output the minimum costs $\bmod 10^9+7$ . And for the second line, output the maximum costs $\bmod 10^9+7$

来源：2021“MINIEYE杯”中国大学生算法设计超级联赛（5）1007