题目描述

森林里有一口深深的魔法井，井水上有一些百合。你有一个大空篮子和一些硬币，正站在井边。你的硬币数量比井中的百合数量还多。井已经注意到你的篮子现在是空的。

如果你往井里投入 $1$ 枚硬币，井就会往你的篮子里抛出 $1$ 朵百合。如果你一次往井里投入 $4$ 枚硬币，井就会记下到目前为止它已经往你的篮子里抛出了多少朵百合。如果你一次往井里投入 $2$ 枚硬币，井就会往你的篮子里抛出它上次记下的那么多朵百合。如果你一次投入 $1$ 枚或 $2$ 枚硬币，但井中剩余的百合不够，那么井就不会抛出任何百合。

给定井中初始的百合数量 $L$，请返回你需要往井里投入的最少硬币数，使得井能把它所有的百合都抛进你的篮子里。

输入格式

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

每行包含一个整数 $L$，表示井中初始的百合数量。

输出格式

对于每个测试用例，输出一行，格式为 Case #x: y，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是需要投入的最少硬币数。

2
5
20

Case #1: 5
Case #2: 15

提示

对于测试用例 #1，当井中有 $5$ 朵百合时，所需的最少硬币数为 $5$。我们一次投 $1$ 枚硬币，井一次抛出 $1$ 朵百合。没有其他操作序列能得到更好的结果，因此答案为 $5$。

对于测试用例 #2，首先，我们一次投 $1$ 枚硬币，共投 $5$ 次，井一次抛出 $1$ 朵百合，共抛出 $5$ 朵。接着，我们一次投 $4$ 枚硬币，井记下到目前为止已经抛出了 $5$ 朵百合。然后，我们一次投 $2$ 枚硬币，井抛出了 $5$ 朵（它记下的数量）百合。我们再投一次 $2$ 枚硬币，井又抛出了 $5$ 朵百合。最后，我们再投一次 $2$ 枚硬币，井抛出了最后 $5$ 朵百合。总共需要的硬币数为 $15$。无法用更少的硬币从井中取出 $20$ 朵百合，因此答案为 $15$。

限制条件

测试集 1

$1 \le T \le 20$

$1 \le L \le 20$

测试集 2

$1 \le T \le 100$

$1 \le L \le 10^5$

翻译由 DeepSeek V4 Pro 完成