사전

문제 정보

    • 문제 ID
    • 시간 제한
    • 메모리 제한
    • 제출 횟수
    • 정답 횟수 (비율)
    • 출제자
    • 출처
    • 분류

문제

(주의: 이 문제는 TopCoder SRM428 Div2 Hard 의 번역 문제입니다.)

ab 로만 이루어진 단어들을 담고 있는 사전이 있다. 이 사전은 n 개의 am 개의 b 로 이루어진 단어들을 _전부_ 포함하는데, 예를 들어 n=2, m=2 인 경우, 사전에는 aabb, abba 등의 단어들이 포함된다.

nm 이 주어질 때, 이 사전의 k 번째 단어를 출력하는 프로그램을 작성하라. 단어들은 사전 순서대로 정렬되어 있다고 가정한다.

입력

입력의 첫 줄에는 테스트 케이스의 수 C (<= 50) 가 주어진다. 각 테스트 케이스의 첫 줄에 n, m (0 <= n, m <= 100) 그리고 k (1 <= k <= 100,000,000) 가 주어진다.

출력

각 테스트 케이스마다 사전의 해당 단어를 한 줄에 출력한다. 만약 사전의 k 번째 단어가 없을 경우 (사전의 단어 수가 k 보다 적을 경우) 에는 NONE 을 출력한다.

예제 입력

4
5 2 11
5 6 17
1 1 2
4 0 2

예제 출력

abaaaab
aaabbabbbab
ba
NONE

노트