4854 - [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 小的无界单词。

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

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