https://code.google.com/codejam/contest/3314486/dashboard#s=p2

Question in brief - :

Hannah is working on a new language which consists only of first L lowercase letters of the English alphabet.

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 Kth smallest among all the words she has written.

Input

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.

Input

2

2 3 4

2 3 9

Output

Case #1: 3

Case #2: 0

Explanation : 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.