For a word $S$, if there exists a length $l$ such that $0 < l < \text{length}(S)$ and the prefix of $S$ of length $l$ is equal to the suffix of $S$ of length $l$, JYY calls $S$ "bounded". For example, "aabaa" and "ababab" are both bounded strings. If a word does not have such an $l$, JYY calls it an "unbounded word".

Now consider all strings of length $N$ consisting only of the letters 'a' and 'b'. JYY wants to know:

(1) How many unbounded words are there in total? (2) Among these unbounded words, which one is the $K$-th smallest in lexicographical order?

Input

The input contains multiple test cases. The first line contains a positive integer $T$, representing the number of test cases. The next $T$ lines each contain two positive integers $N$ and $K$, representing a test case.

Output

For each test case, output two lines. The first line contains an integer representing the number of unbounded words of length $N$. The second line contains a string of length $N$ representing the $K$-th smallest unbounded word.

Constraints

For 20% of the data, $N \le 20$. For 100% of the data, $1 \le T \le 5$, $1 \le N \le 64$. The input guarantees that for any test case, the $K$-th smallest unbounded word always exists.

Examples

Input 1

5
5 1
5 2
5 3
5 4
5 5

Output 1

12
aaaab
12
aaabb
12
aabab
12
aabbb
12
ababb