P5770 [JSOI2016] Unbordered Words

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?

**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.

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.

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