#2078. 「JSOI2016」无界单词

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

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

现在考虑所有仅由字母 ab 组成的长度为 N 的字符串,JYY想知道:

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

输入格式

本题有多组数据。

第一行包含一个正整数 T ,表示测试数据的组数;
接下来 T 行,每行包含两个正整数 N K ,表示一组测试数据。

输出格式

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

其中第一行包含一个整数,表示长度为 N 的无界单词的数量;
其中第二行包含一个长度为 N 的字符串,表示第 K 小的无界单词。

样例

样例输入

5
5 1
5 2
5 3
5 4
5 5

样例输出

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