For a string $s$ of length $n$ consisting only of characters $\texttt{a}, \texttt{b}, \dots, \texttt{z}$, consider an undirected weighted graph with $n$ vertices. For every pair of distinct vertices $i, j$ ($i \neq j$), there is an edge with weight $\text{LCP}(suf_i, suf_j)^\dagger$, where $suf_i = s[i : n]$. Ecrade_ defines the value of string $s$ as the sum of edge weights of the Maximum Spanning Tree of this graph. Ecrade_ asks you to find any string of length $n$ consisting only of $\texttt{a}, \texttt{b}, \dots, \texttt{z}$ that has the $k$-th smallest value.

$^\dagger \text{LCP}(s_1, s_2)$ is defined as the length of the longest common prefix of strings $s_1$ and $s_2$.

Input

The input is read from standard input. The first line contains an integer $T$ ($1 \le T \le 2 \times 10^5$), representing the number of test cases. For each test case, the input contains two integers $n, k$ ($1 \le n, \sum n \le 4 \times 10^5, 1 \le k \le \min(26^n, 10^{15})$).

Output

The output is written to standard output. For each test case, output the $k$-th smallest value on the first line, and the $k$-th smallest string of length $n$ on the second line. If there are multiple strings that satisfy the condition, output any one of them.

Examples

Input 1

3
2 1
2 676
3 16000

Output 1

0
hi
1
gg
1
qwq

Note

• For the first test case, among strings of length 2, the 1st smallest (i.e., the minimum) value is 0. One string that satisfies the condition is hi. Of course, strings like ab and yz also satisfy the condition.
• For the second test case, among strings of length 2, the 676th smallest (i.e., the maximum) value is 1. One string that satisfies the condition is gg. Of course, strings like aa and zz also satisfy the condition.
• For the third test case, among strings of length 3, the 16000th smallest value is 1. One string that satisfies the condition is qwq. Of course, strings like cpp and lol also satisfy the condition.