Fish is standing at position $0$ on an axis. He wants to move to position $K$ now but he has to jump in a really strange way!
There are three choices: $1$,$2$ and $3$ and each time he can choose and use exactly one choice. Each choice can be used for infinite times. When he chooses an unused choice $j$, he will jump forward $j$ step(s). And when he chooses an used choice $j$ again, he will jump $x + 3$ steps forward, where $x$ is the number of steps that he jumped in the last time he chose this choice.
Please help Fish figure out what's the minimum number of times needed, and the total number of ways he can choose no matter the total number of times.
The first line of input contains an integer $T$, representing the number of test cases.
Then for each test case there is exactly one number $K$ which is mentioned above in one line.
For each test case, you should output *Case $x$: $y$ $z$* in one line, where $x$ indicates the case number starting from $1$, $y$ is the minimum number of times needed and $z$ is the total number of ways no matter the total number of times. Since $z$ can be very large, you should output $z bmod (10^9 + 7)$ instead.
$1 <= T <= 200$
$1 <= K <= 10^7$
For $90 %$ test cases: $K <= 1000$
## Input
The first line of input contains an integer $T$, representing the number of test cases.Then for each test case there is exactly one number $K$ which is mentioned above in one line.
## Output
For each test case, you should output *Case $x$: $y$ $z$* in one line, where $x$ indicates the case number starting from $1$, $y$ is the minimum number of times needed and $z$ is the total number of ways no matter the total number of times. Since $z$ can be very large, you should output $z bmod (10^9 + 7)$ instead.
[samples]
## Note
$1 <= T <= 200$$1 <= K <= 10^7$For $90 %$ test cases: $K <= 1000$
**Definitions**
Let $ n \in \mathbb{Z} $ be the side length of a square grid.
Let $ G = (a_{i,j})_{1 \le i,j \le n} $ be an $ n \times n $ matrix of integers, where $ a_{i,j} \in \mathbb{Z}^+ $.
An *island* rooted at $ (i_0, j_0) $ is the maximal connected set of cells $ S \subseteq \{1,\dots,n\} \times \{1,\dots,n\} $ such that:
- $ (i_0, j_0) \in S $,
- For all $ (i,j) \in S $, $ a_{i,j} \ge a_{i_0,j_0} $,
- $ S $ is connected via 4-directional (cardinal) adjacency.
The *value* of an island $ S $ rooted at $ (i_0,j_0) $ is $ v(S) = a_{i_0,j_0} \cdot |S| $.
**Constraints**
1. $ 1 \le n \le 500 $
2. $ 1 \le a_{i,j} \le 10^9 $ for all $ 1 \le i,j \le n $
**Objective**
Find the island $ S^* $ maximizing $ v(S) $.
If multiple islands achieve the same maximum value, select the one with the largest $ |S| $.
Output $ \left( v(S^*), |S^*| \right) $.