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