407518: GYM102821 J Jump on Axis

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.

3
5
14
100

Case 1: 2 3
Case 2: 4 10
Case 3: 8 111211

$$$1 \le T \le 200$$$

$$$1 \le K \le 10^7$$$

For $$$90\%$$$ test cases: $$$K \le 1000$$$