중간자

Alice와 Bob은 서로 다른 나라에 살지만 서로를 굳게 믿는 친구다. 어느 날 Bob은 세상을 바꿀 스타트업 아이디어를 떠올렸지만 자금이 필요했다. Alice는 필요한 돈을 주기로 했다. Bob에게는 은행 계좌가 없어서, Alice는 Bob과 같은 도시에 사는 친구 Eve에게 돈을 보내겠다고 했고, Bob은 Eve에게 비밀 코드만 말하면 돈을 받을 수 있다.

인터넷으로 대화했기 때문에 Alice는 누군가 대화를 엿듣고 비밀 코드를 들을까 걱정했다. Bob은 Alice가 만난 사람 중 가장 뛰어난 머리를 가졌으므로, Alice는 특정 함수로 해시한 코드를 Bob에게 알려 주기로 했고, 누군가 대화를 엿들어도 Bob이 먼저 비밀 코드를 알아낼 것이라 믿었다. Bob은 코드에 대해 다음을 알고 있다.

• 코드의 길이는 L이다.
• 코드는 문자 ‘A’..‘Z’(대문자만)로만 이루어진다.
• 해시를 계산하는 공식: [\left(\left( \sum_{i=1}^{L-1}{n_i \times M^{L-i}} \right) + n_L \right) \mod {10007}]
• n_i는 i번째 위치(1 ≤ i ≤ L)의 문자를 나타내는 숫자 값이며, A = 0, B = 1, C = 2, . . . , Z = 25이다.
• 코드는 위 함수로 주어진 값 H로 해시되는 ‘A’..‘Z’로 이루어진 문자열 중 사전순으로 가장 작은 문자열이다.

누군가 먼저 알아내기 전에 Bob이 비밀 코드를 빨리 알아낼 수 있게 도와줄 수 있는가?

프로그램은 하나 이상의 테스트 케이스로 시험된다. 입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. (1 ≤ T ≤ 100)

각 테스트 케이스는 공백으로 구분된 세 정수가 있는 한 줄로 이루어진다.

• L: 비밀 코드의 길이 (1 ≤ L ≤ 100, 000)
• H: 코드의 해시 값 (0 ≤ H < 10, 007)
• M: 해시 공식에 쓰이는 승수 (0 ≤ M ≤ 20)

각 테스트 케이스마다, 그러한 문자열을 찾을 수 있으면 비밀 코드를 한 줄에 출력하고, 없으면 ‘None’을 출력한다. (따옴표는 명확성을 위해 표기한 것이다.)