GUESSN5

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 w times 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 three single-space separated integers n, w and m, where n is the size of the game, w is the maximal number of lies 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 ≤ w ≤ 2⁴

2 ≤ n ≤ 2¹²

(2w+1) * ⌈log₂ n⌉ ≤ m

0 ≤ q ≤ m

Example

Input:
4
2 2 6
2 3 8
2 16 34
5 2 18

One of possible output is:
6
01
01
01
01
01
01
6
01
01
01
01
01
01
0
15
00011
00011
00011
00011
00011
01010
01010
01010
01010
01010
00100
00101
00110
01100
01111

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 "YYYYYY", "NNNNNN" (without lie), "YYYYYN", "YYYYNY", "YYYNYY", "YYNYYY", "YNYYYY", "NYYYYY", "NNNNNY", "NNNNYN", "NNNYNN", "NNYNNN", "NYNNNN", "YNNNNN", (with one lie) or "NNNNYY", "NNNYNY", "NNNYYN", "NNYNNY", "NNYNYN", "NNYYNN", "NYNNNY", "NYNNYN", "NYNYNN", "NYYNNN", "YNNNNY", "YNNNYN", "YNNYNN", "YNYNNN", "YYNNNN", "NNYYYY", "NYNYYY", "NYYNYY", "NYYYNY", "NYYYYN", "YNNYYY", "YNYNYY", "YNYYNY", "YNYYYN", "YYNNYY", "YYNYNY", "YYNYYN", "YYYNNY", "YYYNYN", "YYYYNN" (with 2 lies). The other replies ("NNNYYY", "NNYNYY", "NNYYNY", "NNYYYN", "NYNNYY", "NYNYNY", "NYNYYN", "NYYNNY", "NYYNYN", "NYYYNN", "YNNNYY", "YNNYNY", "YNNYYN", "YNYNNY", "YNYNYN", "YNYYNN", "YYNNNY", "YYNNYN", "YYNYNN", "YYYNNN") are not ok, because for every of them and for every possible x value, the Judge lies more than two times. For each good reply, there is only one integer from range [1, 2], that match this replies ("match" means match all except at most two of queries). The score is 6² = 36. Notice, that You can use the same query more than once.

In 2nd test case player tried to give the solution, but the solution is wrong. The Judge can reply for example "YYYNNN" and then for both possible values of x the judge lied 3 times. Player needs more queries in this case. The score is penalty score 4 * 8² = 256.

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

In 4th 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 15² = 225.

Total score is 36 + 256 + 4624 + 225 = 5141.

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