P16655 [GKS 2018 #F] Palindromic Sequence

Hannah is working on a new language which consists only of first $L$ lowercase letters of the English alphabet. She is obsessed with palindromes, which are words that read the same forward and backward, e.g hannah and civic. She has written down all of the words in her language of length at most $N$, that are also palindromes. Now, she is interested in finding the length of the word that is lexicographically $K^{th}$ smallest among all the words she has written. A word composed of ordered letters $a_1$, $a_2$, ..., $a_p$ is lexicographically smaller than word $b_1$, $b_2$, ..., $b_q$ if $a_i < b_i$, where i is the first index where characters differ in the two words. Also, a prefix of a word is considered lexicographically smaller than the word itself. For example, the following words are arranged in lexicographically increasing order: a, aa, aba, cabac, d.

The first line of the input gives the number of test cases, $T$. $T$ test cases follow. Each test case consists of one line containing three integers L, N, and K, as described above.

For each test case, output one line containing 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$.

In Sample Cases #1 and #2, Hannah's language consists only of the letters a and b. All the palindromic words of length at most $3$ in her language, in lexicographic order, are: $a$, $aa$, $aaa$, $aba$, $b$, $bab$, $bb$ and $bbb$. In Sample Case #1, the fourth-smallest word is $aba$, which is $3$ characters long, so we output $3$. In Sample Case #2, $K$ exceeds the total number of possible words, and hence we output $0$. ### Limits $1 \le T \le 100$. $1 \le L \le 26$. $1 \le K \le 10^{12}$. **Small dataset (Test set 1 - Visible)** $1 \le N \le 100$. **Large dataset (Test set 2 - Hidden)** $1 \le N \le 10^{12}$.