311037: CF1925A. We Got Everything Covered!

A. We Got Everything Covered!time limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

You are given two positive integers $n$ and $k$.

Your task is to find a string $s$ such that all possible strings of length $n$ that can be formed using the first $k$ lowercase English alphabets occur as a subsequence of $s$.

If there are multiple answers, print the one with the smallest length. If there are still multiple answers, you may print any of them.

Note: A string $a$ is called a subsequence of another string $b$ if $a$ can be obtained by deleting some (possibly zero) characters from $b$ without changing the order of the remaining characters.

Input

The first line of input contains a single integer $t$ ($1\leq t\leq 676$) denoting the number of test cases.

Each test case consists of a single line of input containing two integers $n$ ($1\leq n\leq 26$) and $k$ ($1\leq k\leq 26$).

Output

For each test case, print a single line containing a single string $s$ which satisfies the above property. If there are multiple answers, print the one with the smallest length. If there are still multiple answers, you may print any of them.

ExampleInput

4
1 2
2 1
2 2
2 3

Output

ab
aa
baab
abcbac

Note

For the first test case, there are two strings of length $1$ which can be formed using the first $2$ lowercase English alphabets, and they are present in $s$ as a subsequence as follows:

• $\texttt{a}: {\color{red}{\texttt{a}}}\texttt{b}$
• $\texttt{b}: \texttt{a}{\color{red}{\texttt{b}}}$

For the second test case, there is only one string of length $2$ which can be formed using the first lowercase English alphabet, and it is present in $s$ as a subsequence as follows:

• $\texttt{aa}: {\color{red}{\texttt{aa}}}$

For the third test case, there are $4$ strings of length $2$ which can be formed using the first $2$ lowercase English alphabets, and they are present in $s$ as a subsequence as follows:

• $\texttt{aa}: \texttt{b}{\color{red}{\texttt{aa}}}\texttt{b}$
• $\texttt{ab}: \texttt{ba}{\color{red}{\texttt{ab}}}$
• $\texttt{ba}: {\color{red}{\texttt{ba}}}\texttt{ab}$
• $\texttt{bb}: {\color{red}{\texttt{b}}}\texttt{aa}{\color{red}{\texttt{b}}}$

For the fourth test case, there are $9$ strings of length $2$ which can be formed using the first $3$ lowercase English alphabets, and they are present in $s$ as a subsequence as follows:

• $\texttt{aa}: {\color{red}{\texttt{a}}}\texttt{bcb}{\color{red}{\texttt{a}}}\texttt{c}$
• $\texttt{ab}: {\color{red}{\texttt{ab}}}\texttt{cbac}$
• $\texttt{ac}: \texttt{abcb}{\color{red}{\texttt{ac}}}$
• $\texttt{ba}: \texttt{abc}{\color{red}{\texttt{ba}}}\texttt{c}$
• $\texttt{bb}: \texttt{a}{\color{red}{\texttt{b}}}\texttt{c}{\color{red}{\texttt{b}}}\texttt{ac}$
• $\texttt{bc}: \texttt{a}{\color{red}{\texttt{bc}}}\texttt{bac}$
• $\texttt{ca}: \texttt{ab}{\color{red}{\texttt{c}}}\texttt{b}{\color{red}{\texttt{a}}}\texttt{c}$
• $\texttt{cb}: \texttt{ab}{\color{red}{\texttt{cb}}}\texttt{ac}$
• $\texttt{cc}: \texttt{ab}{\color{red}{\texttt{c}}}\texttt{ba}{\color{red}{\texttt{c}}}$

题目大意：
给定两个正整数n和k，需要找到一个字符串s，使得所有可以用前k个小写英文字母组成的长度为n的可能字符串都是s的子序列。如果有多个答案，输出其中长度最小的一个。如果仍然有多个答案，可以输出其中任意一个。

输入数据格式：
第一行输入一个整数t（1≤t≤676），表示测试用例的数量。
每个测试用例占一行，包含两个整数n（1≤n≤26）和k（1≤k≤26）。

输出数据格式：
对于每个测试用例，输出一行满足上述性质的字符串s。如果有多个答案，输出其中长度最小的一个。如果仍然有多个答案，可以输出其中任意一个。

公式（使用LaTeX格式）：
无具体的数学公式，只需理解子序列的定义：字符串a是字符串b的子序列，如果a可以通过删除b中的一些（可能为零）字符而不改变剩余字符的顺序来得到。题目大意： 给定两个正整数n和k，需要找到一个字符串s，使得所有可以用前k个小写英文字母组成的长度为n的可能字符串都是s的子序列。如果有多个答案，输出其中长度最小的一个。如果仍然有多个答案，可以输出其中任意一个。 输入数据格式： 第一行输入一个整数t（1≤t≤676），表示测试用例的数量。 每个测试用例占一行，包含两个整数n（1≤n≤26）和k（1≤k≤26）。 输出数据格式： 对于每个测试用例，输出一行满足上述性质的字符串s。如果有多个答案，输出其中长度最小的一个。如果仍然有多个答案，可以输出其中任意一个。 公式（使用LaTeX格式）： 无具体的数学公式，只需理解子序列的定义：字符串a是字符串b的子序列，如果a可以通过删除b中的一些（可能为零）字符而不改变剩余字符的顺序来得到。