GUESSN4

Judge has chosen an integer x in the range [1, n]. Your task is to find x, using at most m queries as described below. But be careful, because there are 2 important things:

1. The Judge can lie. Judge is allowed to lie only once in single game and only in reply for query.

2. You must prepare all queries at once and send all of them to the Judge before You got any reply.

Query

Single query should contains string s₁s₂s₃...s_n, where s_i is '0' or '1'. The reply for query is "YES", if s_x = '1', or "NO" otherwise.

For example, when n=8, x=5 and query is "00101011", the Judge will reply "YES" (if telling the truth) or "NO" (if lying), because the 5th character in query is '1'.

Real task and scoring

The real task is not to find the number x chosen by Judge, but only to prepare queries, which allow You to guess the x value for every possible Judge's reply. The Judge won't give You reply for Your queries.

If the Judge will find such reply for Your queries, that there will be more than one x value possible, You will fail the test case (see example for detail explanation). Otherwise You succeed.

If You succeed, Your score is q², where q is the number of queries, that You use. If You fail, You got penalty score equal to 4m². Total score is the sum of scores of single games. The smaller score is the better score.

Input

The first line of input contains one integer T - the number of test cases. Then T test cases follow.

Each test case contains one line with two single-space separated integers n and m, where n is the size of the game and m is the maximal number of queries, that You can use.

Output

For each test case print a line with one integer q - the number of queries that You want to ask.

Then print q lines with Your queries. Each query should be string of length n, with all characters '0' or '1'.

Constraints

1 ≤ T ≤ 2⁷

2 ≤ n ≤ 2¹⁶

3 ⌈log₂ n⌉ ≤ m

0 ≤ q ≤ m

For bigger tests, number of test cases is smaller (T ≤ 40 for 10000 ≤ m ≤ 20000, T ≤ 20 for 20000 ≤ n ≤ 30000, T ≤ 10 for 30000 ≤ n)

Example

Input:
5
2 4
3 9
32 32
4 10
5 12

One of possible output is:
4
01
01
10
10
9
001
001
001
010
010
010
100
100
100
0
2
0011
0110
6
00011
00101
00110
01110
01101
01011

Explanation:

Notation: reply "YYN..." means, that Judge replied "YES" for first and second query, "NO" for third query, and so on...

In 1st test case there are only two numbers. Judge can reply "YYNN", "NNYY" (without lie) or "YNNN", "NYNN", "YYNY", "YYYN", "NYYY", "YNYY", "NNNY", "NNYN" (with one lie). The other replies ("YYYY", "NNNN", "YNYN", "YNNY", "NYNY", "NYYN") are not ok, because for every of them and for every possible x value, the Judge lies more than once. For each good reply, there is only one integer from range [1, 2], that match this replies ("match" means match all except at most one of queries). The score is 4² = 16. Notice, that You can use the same query more than once.

In 2nd test case player asked three times for every single integer. Because Judge can lie only once, the player is able to detect the lie, and choose the value x correctly. The score is 9² = 81.

In 3rd test case player decided to skip. Player got the penalty score 4 * 32² = 4096.

In 4th test case player tried to give the solution, but the solution is wrong. There is impossible to guess the x value in only two queries. The Judge can reply for example "YY" and then x can be 2, 3 or 4. The score is penalty score 4 * 10² = 400.

In 5th test case the nubmer of queries given by player is smaller than the maximal possible number. For every possible Judge's reply there is only one possible value of x, so test succeeded. The score is 6² = 36.

Total score is 16 + 81 + 4096 + 400 + 36 = 4629.

Similar problems

There is a family of similar problems. Here is the table with them:

subset - the query is about any subset of {1,2,...,n}
range - the query is about any range [a,b]
 interactive - the Judge replies after every query
non-interactive - all queries have to be asked at once, before any reply