小鱼站在坐标轴的 0 位置。他现在想移动到位置 $K$，但他必须以一种非常奇怪的方式跳跃！

这里有三种选择：1、2 和 3，每次他可以选择并使用其中恰好一种选择。每种选择都可以无限次使用。当他选择一个尚未使用的选择 $j$ 时，他会向前跳 $j$ 步。而当他再次选择一个已经使用过的选择 $j$ 时，他会向前跳 $x + 3$ 步，其中 $x$ 是他上次选择该选项时跳跃的步数。

请帮助小鱼算出他到达位置 $K$ 所需的最少跳跃次数，以及无论总跳跃次数是多少，他到达位置 $K$ 的总方案数。

输入格式

输入的第一行包含一个整数 $T$，表示测试用例的数量。 对于每个测试用例，只有一行，包含一个整数 $K$。

输出格式

对于每个测试用例，请输出一行 Case x: y z，其中 $x$ 表示从 1 开始的用例编号，$y$ 是所需的最少跳跃次数，$z$ 是无论总跳跃次数是多少时的总方案数。由于 $z$ 可能非常大，请输出 $z \pmod{10^9 + 7}$。

样例

样例输入 1

3
5
14
100

样例输出 1

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

数据范围

$1 \le T \le 200$ $1 \le K \le 10^7$ 对于 90% 的测试用例：$K \le 1000$