[JSOI2016] 无界单词

题目描述

对于一个单词 $S$ ,如果存在一个长度 $l$,满足 $0 < l < |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$ 小的无界单词。