题目描述

我们称一个数是漂亮的，如果它仅由数字 1 重复一次或多次组成。并非所有数字都是漂亮的，但我们可以通过将任何十进制正整数写成另一种进制来使其变得漂亮。

给定整数 $N$，你能找到一个进制 $B$（$B > 1$），使得 $N$ 在该进制下的所有数字都是 1 吗？如果存在多个满足该性质的进制，请选择使得数字 1 的个数最多的那个。

输入格式

输入的第一行给出测试用例的数量 $T$。接下来有 $T$ 个测试用例。每个测试用例由一行一个整数 $N$ 组成。

输出格式

对于每个测试用例，输出一行，格式为 Case #x: y，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是题目描述中所说的进制。

2
3
13

2
3

提示

在样例 #1 中，最优解是将 3 写作 $11_2$（二进制）。

在样例 #2 中，最优解是将 13 写作 $111_3$（三进制）。注意，我们也可以将 13 写作 $11_{12}$（十二进制），但这些表示中的 1 的个数都不如前者多。

限制条件

$1 \le T \le 100$。

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

$3 \le N \le 1000$。

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

$3 \le N \le 10^{18}$。

翻译由 DeepSeek V4 Pro 完成