套娃（matryoshka）是一种起源于俄罗斯的玩偶，已有超过一个世纪的历史。其定义特征是它们由一套大小各异的玩偶组成，较小的玩偶可以完美地嵌套在较大的玩偶内部。

在本题中，我们研究“套多边形”（matrygon），这是一组遵循类似嵌套模式的正凸多边形。一个套多边形由一组面积为正的正凸多边形组成，使得对于所有 $i$，多边形 $p_{i+1}$ 的顶点与多边形 $p_i$ 的顶点的真子集重合（$p_{i+1}$ 的顶点数严格少于 $p_i$ 的顶点数）。

例如，下图展示了两个套多边形。第一个包含 3 个正凸多边形：一个正二十四边形（24 条边）、一个正六边形（6 条边）和一个等边三角形（3 条边）。第二个包含 2 个正凸多边形：一个正二十二边形（22 条边）和一个正十一边形（11 条边）。这两个套多边形中所有多边形的边数之和均为 33。

给定一个固定的总边数 $N$，计算一个套多边形中最多能包含多少个多边形，使得其中所有多边形的边数之和恰好为 $N$。

输入格式

输入的第一行包含测试用例的数量 $T$。接下来有 $T$ 行，每行代表一个测试用例，包含一个整数 $N$，即目标总边数。

输出格式

对于每个测试用例，输出一行 Case #x: y，其中 $x$ 是测试用例编号（从 1 开始），$y$ 是套多边形中多边形的最大数量，使得所有多边形的边数之和恰好为 $N$。

数据范围

$1 \le T \le 100$。 $3 \le N \le 10^6$。

样例

样例输入 1

3
33
15
41

样例输出 1

Case #1: 3
Case #2: 2
Case #3: 1

说明

题目描述中展示的第一个套多边形是样例 1 的最优解。

在样例 2 中，我们可以通过将一个正五边形（5 条边）嵌套在一个正十边形（10 条边）内得到两个多边形。

在样例 3 中，无法创建包含多个正多边形的套多边形，因此唯一的选择是使用一个单独的正四十一边形（41 条边）。