题目描述

John 喜欢玩电脑游戏。他最近发现了一个有趣的游戏。游戏中有 $N$ 个格子，排成一行，从左到右编号为连续的整数，从 $1$ 开始。最初，所有格子都是 白色 的。如果一个格子是 白色 且没有任何相邻的 红色 格子，则该格子是有效的。每一轮，玩家可以将任意一个有效格子涂成 红色。当没有有效格子时，游戏结束。玩家的得分等于他涂红的格子数量。

为了精通这个游戏，John 正在与一个机器人对战。这个机器人训练得不太好，它总是涂最左边的有效格子。而 John 则非常谨慎，他可以任意选择有效格子。机器人先手，双方轮流进行。

假设 John 以最优方式（最小化对手的得分）进行游戏，求机器人能获得的最大得分。

输入格式

输入的第一行给出测试用例的数量 $T$。接下来有 $T$ 个测试用例。

每个测试用例只有一行，包含一个整数 $N$，表示游戏中的格子数量。

输出格式

对于每个测试用例，输出一行，格式为 Case #x: y，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是在 John 最优游戏的情况下机器人能获得的最大得分。

3
1
3
6

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

提示

在样例 #1 中，$N = 1$ 个格子。机器人能获得的最大得分为 $1$。

• 第一步：机器人将第一个格子涂红。

由于没有更多可行操作，游戏结束。因此答案为 $1$。

在样例 #2 中，$N = 3$ 个格子。机器人能获得的最大得分为 $1$。

:::align{center} :::

• 第一步：机器人将第一个格子涂红。
• 第二步：John 将第三个格子涂红。

由于没有更多可行操作，游戏结束。因此答案为 $1$。

在样例 #3 中，$N = 6$ 个格子。机器人能获得的最大得分为 $2$。在此样例中存在多种解法，其中之一为：

:::align{center} :::

• 第一步：机器人将第一个格子涂红。
• 第二步：John 将第三个格子涂红。
• 第三步：机器人将第五个格子涂红。

由于没有更多可行操作，游戏结束。因此答案为 $2$。

限制条件

$1 \le T \le 100$。

$1 \le N \le 10^5$。

测试集 1

$1 \le N \le 10$。

测试集 2

$1 \le N \le 10^5$。

翻译由 DeepSeek V4 Pro 完成