Comet OJ

C0837 [JSOI2016]无界单词

内存限制：512 MB 时间限制：1000 ms

题目描述

对于一个单词 $S$，如果存在一个长度 $l$，满足 $0\lt l\lt |S|$，并且使得 $S$ 长度为 $l$ 的前缀与 $S$ 长度为 $l$ 的后缀相同，JYY 则称 $S$ 是有界的。比如aabaa和ababab就都是有界的字符串。如果一个单词不存在这样的 $l$，则 JYY 称之为无界单词。

现在考虑所有仅由字母a和b组成的长度为 $N$ 的字符串，JYY 想知道：

  1. 一共有多少个无界单词？
  2. 这些无界单词中，按字典序排列第 $K$ 小的单词是哪一个？

输入格式

本题有多组数据。

第一行包含一个正整数 $T$，表示测试数据的组数；

接下来 $T$ 行，每行包含两个正整数 $N$ 和 $K$，表示一组测试数据。

输出

对于每一个测试数据，输出两行。

其中第一行包含一个整数，表示长度为 $N$ 的无界单词的数量；

其中第二行包含一个长度为 $N$ 的字符串，表示第 $K$ 小的无界单词。

样例

样例输入 1

5
5 1
5 2
5 3
5 4
5 5

样例输出 1

12
aaaab
12
aaabb
12
aabab
12
aabbb
12
ababb

提示

对于 $20\%$ 的数据，满足 $N\le 20$；

对于全部数据，满足 $1\le T\le 5,1\le N\le 64$，并且保证对于任意测试数据，总存在第 $K$ 小的无界单词。