题目描述

Hannah 正在研究一门新语言，该语言仅由英文字母表的前 $L$ 个小写字母组成。她痴迷于回文（即正读反读都相同的单词，例如 hannah 和 civic）。她写下了自己语言中所有长度不超过 $N$ 且为回文的单词。

现在，她希望找出在她写下的所有单词中，字典序第 $K$ 小的单词的长度。单词 $a_1 a_2 \dots a_p$ 字典序小于单词 $b_1 b_2 \dots b_q$，如果存在第一个位置 $i$ 使得 $a_i < b_i$，且在此之前的字符均相同。此外，一个单词的前缀被认为字典序小于该单词本身。例如，以下单词按字典序递增排列：a，aa，aba，cabac，d。

输入格式

输入的第一行给出测试用例的数量 $T$。接下来有 $T$ 个测试用例。每个测试用例由一行包含三个整数 $L$、$N$ 和 $K$ 组成，含义如上所述。

输出格式

对于每个测试用例，输出一行，格式为 Case #x: y，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是 Hannah 语言中所有长度不超过 $N$ 的回文单词中字典序第 $K$ 小的单词的长度。如果不存在这样的单词，则输出 $0$。

2
2 3 4
2 3 9

Case #1: 3
Case #2: 0

提示

在样例 #1 和 #2 中，Hannah 的语言仅包含字母 a 和 b。她语言中所有长度不超过 $3$ 的回文单词按字典序排列为：a、aa、aaa、aba、b、bab、bb、bbb。

在样例 #1 中，第 $4$ 小的单词是 aba，长度为 $3$，因此输出 $3$。

在样例 #2 中，$K$ 超过了可能单词的总数，因此输出 $0$。

限制条件

$1 \le T \le 100$。

$1 \le L \le 26$。

$1 \le K \le 10^{12}$。

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

$1 \le N \le 100$。

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

$1 \le N \le 10^{12}$。

翻译由 DeepSeek V4 Pro 完成