#### Statement

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:

- The Judge can lie. Judge is allowed to lie
*w*times in single game and only in reply for query. - 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 _{1}s_{2}s_{3}...s_{n}*, where

*s*is '0' or '1'. The reply for query is "YES", if

_{i}*s*= '1', or "NO" otherwise.

_{x}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 5^{th} 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 ^{2}*, where

*q*is the number of queries, that you use. If you fail, you got penalty score equal to 4*

*m*. Total score is ⌊(the sum of scores of single games) / 100⌋. The smaller score is the better score.

^{2}#### 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^{7} - 2 ≤
*w*≤ 2^{4} - 2 ≤
*n*≤ 2^{12} - (2*
*w*+1) * ⌈log_{2}*n*⌉ ≤*m* - 0 ≤
*q*≤*m*

#### Example input:

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

#### Example output:

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

#### Time and memory limit:

- 1 second
- 64MB

#### Explanation:

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

In 1^{st} 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^{2} = 36. Notice, that You can use the same query more than once.

In 2^{nd} 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^{2} = 256.

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

In 4^{th} 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^{2} = 225.

Total score is ⌊(36 + 256 + 4624 + 225) / 100⌋ = 51.

**Problem source:**
SPOJ