회문 수열

Hannah는 영어 알파벳의 처음 L개 소문자로만 구성된 새로운 언어를 만들고 있다. 그녀는 앞에서 읽으나 뒤에서 읽으나 같은 단어인 회문에 푹 빠져 있으며, 예를 들면 hannah와 civic가 있다. 그녀는 자신의 언어에 속하는 길이가 최대 N인 단어 중 회문이기도 한 모든 단어를 적어 두었다.

이제 그녀는 자신이 적어 둔 모든 단어 중 사전순으로 $K^{th}$번째로 작은 단어의 길이를 구하려 한다. 순서가 있는 문자 $a_{1}$, $a_{2}$, ..., $a_{p}$로 구성된 단어와 $b_{1}$, $b_{2}$, ..., $b_{q}$로 구성된 단어를 비교할 때, 두 단어에서 문자가 처음으로 다른 위치의 인덱스가 i이고 $a_{i}$ < $b_{i}$이면 전자가 후자보다 사전순으로 작다. 또한 어떤 단어의 접두사는 그 단어 자체보다 사전순으로 작은 것으로 간주한다. 예를 들어 다음 단어들은 사전순으로 증가하도록 나열되어 있다: a, aa, aba, cabac, d.

제한

1 ≤ T ≤ 100. 시간 제한: 테스트 세트당 20초. 메모리 제한: 1 GB. 1 ≤ L ≤ 26. 1 ≤ K ≤ $10^{12}$.

소규모 데이터 세트 (테스트 세트 1 - 공개)

1 ≤ N ≤ 100.

대규모 데이터 세트 (테스트 세트 2 - 비공개)

1 ≤ N ≤ $10^{12}$.

입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 위에서 설명한 세 정수 L, N, K가 포함된 한 줄로 구성된다.

각 테스트 케이스마다 Case #x: y을 포함하는 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호이며(1부터 시작), y는 Hannah의 언어에서 길이가 최대 N인 모든 회문 단어 중 사전순으로 $K^{th}$번째로 작은 회문 단어의 길이이다. 그러한 단어가 존재하지 않으면 0을 출력한다.

예제 케이스 #1과 #2에서 Hannah의 언어는 문자 a와 b로만 구성된다. 그녀의 언어에서 길이가 최대 3인 모든 회문 단어를 사전순으로 나열하면 다음과 같다: a, aa, aaa, aba, b, bab, bb, bbb.

예제 케이스 #1에서 네 번째로 작은 단어는 aba이며 길이가 3자이므로 3을 출력한다.

예제 케이스 #2에서 K는 가능한 단어의 총개수보다 크므로 0을 출력한다.