Palindromic Sequence

Hannah is working on a new language made only of the first $L$ lowercase letters of the English alphabet. She is obsessed with palindromes, which are words that read the same forward and backward, such as hannah and civic. She has written down every word in her language whose length is at most $N$ and that is also a palindrome.

Find the length of the $K$th smallest palindromic word among all the words she wrote, in lexicographic order. A word $a_1, a_2, \ldots, a_p$ is lexicographically smaller than $b_1, b_2, \ldots, b_q$ if $a_i < b_i$ at the first index $i$ where the two words differ. A prefix of a word is smaller than the word itself. For example, these words are in lexicographically increasing order: a, aa, aba, cabac, d.

The first line contains the number of test cases $T$. Each of the next $T$ lines contains three integers $L$, $N$, and $K$, as described above.

For each test case, print one line in the form Case #x: y, where $x$ is the test case number starting from 1 and $y$ is the length of the lexicographically $K$th smallest palindromic word among all palindromic words of length at most $N$ in Hannah's language. If no such word exists, output 0.

• $1 \le T \le 100$
• $1 \le L \le 26$
• $1 \le K \le 10^{12}$