Problem Description

Given a three-dimensional space of $[1, n] \times [1, n] \times [1, n]$. You're required to place some $1 \times 1 \times 1$ cubes to make this 3D space look $n \times 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.

Input

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 \leq n \leq 10^{18}$.

Output

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

1
2

27
60