题目描述

🌟在遥远的宇宙中，存在一种名为 “纯光编码” 的通信协议。 这种协议有一个非常严格的要求：

一段编码如果在某种进制下，所有数位全部为 1，就被认为是“完美光码”。

星际灯塔会将一个十进制整数能量值 N 转换为某种 进制 B（B > 1） 的表示形式，用来发送信号。

纯光规则

• 如果一个数在某种进制表示下，每一位都是 1，那么这个表示就是一个 完美光码。
• 并不是所有能量值在十进制下都是完美光码，但灯塔可以自由选择进制 B 来进行转换。

你的任务

给定一个十进制整数 N，请你判断：

是否存在一个进制 B（B > 1），使得 N 在 B 进制下的表示 每一位都是 1？

如果存在 多个 这样的进制，请你选择：

能让 1 的数量最多的那个进制（也就是表示长度最长）。

输入格式

第一行：整数 T，表示测试数据的组数  
接下来 T 行：每行一个整数 N

输出格式

对于每一组测试数据，输出一行结果，格式为：

Case #x: y

其中：

• x 是测试数据编号（从 1 开始）
• y 是满足条件的进制 B

数据范围

• 1 ≤ T ≤ 100
• 3 ≤ N ≤ 10^18
• 所有输入均为整数

2
3
13

Case #1: 2
Case #2: 3

样例解释

• 样例 1 能量值 3 在二进制下表示为 11，成功激活纯光编码。

• 样例 2 能量值 13：

  • 在三进制下表示为 111（三位纯光）
  • 在十二进制下表示为 11（两位纯光） 因为三进制下的纯光数量更多，因此选择进制 3。