P16655 [GKS 2018 #F] Palindromic Sequence

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$。

在样例 #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 完成