시간 제한메모리 제한제출정답맞힌 사람정답 비율
20 초 (추가 시간 없음) 1024 MB0000.000%

문제

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 Kth smallest among all the words she has written. A word composed of ordered letters a1, a2, ..., ap is lexicographically smaller than word b1, b2, ..., bq if ai < bi, 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: aaaabacabacd.

입력

The first line of the input gives the number of test cases, TT test cases follow. Each test case consists of one line containing three integers LN, 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 Kth smallest palindromic word among all palindromic words of length at most N in Hannah's language.

If no such word exists, output 0.

제한

  • 1 ≤ T ≤ 100.
  • 1 ≤ L ≤ 26.
  • 1 ≤ K ≤ 1012.

Test Set 1 (22점)

  • 1 ≤ N ≤ 100.

Test Set 2 (30점)

  • 1 ≤ N ≤ 1012.

예제 입력 1

2
2 3 4
2 3 9

예제 출력 1

Case #1: 3
Case #2: 0

채점 및 기타 정보

  • 예제는 채점하지 않는다.