Description

For a word $S$, if there exists a length $l$ such that $0 < l < |S|$, and the prefix of $S$ with length $l$ is the same as the suffix of $S$ with length $l$, then JYY calls $S$ bordered. For example, aabaa and ababab are both bordered strings. If a word does not have such an $l$, then JYY calls it an unbordered word.

Now consider all strings of length $N$ that consist only of the letters a and b. JYY wants to know:

1. How many unbordered words are there in total?
2. Among these unbordered words, when sorted in lexicographical order, what is the $K$-th smallest word?

Input Format

This problem contains multiple test cases.

The first line contains a positive integer $T$, the number of test cases.

The next $T$ lines each contain two positive integers $N$ and $K$, describing one test case.

Output Format

For each test case, output two lines.

The first line contains an integer, the number of unbordered words of length $N$.

The second line contains a string of length $N$, representing the $K$-th smallest unbordered word.

5
5 1
5 2
5 3
5 4
5 5

12
aaaab
12
aaabb
12
aabab
12
aabbb
12
ababb

Hint

For $20\%$ of the testdata, $N \le 20$.

For all testdata, $1 \le T \le 5$, $1 \le N \le 64$, and it is guaranteed that for every test case, the $K$-th smallest unbordered word always exists.

Translated by ChatGPT 5