题目描述

Wheatley 正在参加世界上最好的派对：这里有无限多的蛋糕！每个蛋糕都是一个边长为整数（单位为厘米）的正方形。派对上有所有可能的整数边长的蛋糕，每种都有无限多个。所有蛋糕的厚度相同，因此我们只考虑它们的面积。

Wheatley 决心吃掉一块或多块蛋糕，使得它们的总面积恰好为 $N\ \text{cm}^2$。但出于健康考虑，他希望吃的蛋糕数量尽可能少。你能帮他计算出他最少需要吃多少块蛋糕吗？

输入格式

输入的第一行包含一个整数 $T$，表示测试用例的数量。接下来有 $T$ 个测试用例。每个测试用例由一行一个整数 $N$ 组成，表示 Wheatley 想要吃掉的蛋糕总面积的精确值。

输出格式

对于每个测试用例，输出一行，格式为 Case #x: y，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是 Wheatley 在恰好吃掉总面积 $N$ 的情况下所需的最少蛋糕块数。

3
3
4
5

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

提示

在样例 #1 中，唯一的可行策略是 Wheatley 吃掉三块边长为 $1$ 的蛋糕。

在样例 #2 中，Wheatley 可以吃掉一块边长为 $2$ 的蛋糕，这比吃掉四块边长为 $1$ 的蛋糕所需的块数更少。

在样例 #3 中，最佳策略是 Wheatley 吃掉一块边长为 $2$ 的蛋糕和一块边长为 $1$ 的蛋糕。

限制条件

小数据集（测试集 1 – 可见）

$1 \le T \le 50$。

$1 \le N \le 50$。

大数据集（测试集 2 – 隐藏）

$1 \le T \le 100$。

$1 \le N \le 10000$。

翻译由 DeepSeek V4 Pro 完成