We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. All Contests
  2. HourRank 30
  3. Diverse Strings

Diverse Strings

In this challenge, we introduce the concept of assorted and diversed strings.

  • A string is called assorted if no two distinct letters in appear the same number of times. For example, aacbcc is assorted, but aabaccab is not assorted, since b and c each appears exactly times.
  • A string is called diverse if it is assorted and all its prefixes and suffixes are assorted. For example, aabaa is diverse, but aaba is not diverse, since the suffix ba is not assorted.

Given and , find the lexicographically smallest diverse string of length with exactly distinct letters. Your output string can only contain lowercase English letters. If no such string exists, output NONE.

Input Format

The first line of input contains , the number of queries.

Each query consists of a single line containing two space-separated integers and .

Constraints

Output Format

For each case, output a single line containing the required diverse string, or the string NONE if no such string exists.

Sample Input 0

3
1 1
2 2
5 2

Sample Output 0

a
NONE
aabaa