P16885 [GKS 2022 #E] Coloring Game

John 喜欢玩电脑游戏。他最近发现了一个有趣的游戏。游戏中有 $N$ 个格子，排成一行，从左到右编号为连续的整数，从 $1$ 开始。最初，所有格子都是 **白色** 的。如果一个格子是 **白色** 且没有任何相邻的 **红色** 格子，则该格子是有效的。每一轮，玩家可以将任意一个有效格子涂成 **红色**。当没有有效格子时，游戏结束。玩家的得分等于他涂红的格子数量。 为了精通这个游戏，John 正在与一个机器人对战。这个机器人训练得不太好，它总是涂最左边的有效格子。而 John 则非常谨慎，他可以任意选择有效格子。机器人先手，双方轮流进行。 假设 John 以最优方式（最小化对手的得分）进行游戏，求机器人能获得的最大得分。

输入的第一行给出测试用例的数量 $T$。接下来有 $T$ 个测试用例。 每个测试用例只有一行，包含一个整数 $N$，表示游戏中的格子数量。

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

在样例 #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 完成