If a string $v$ appears in another string $u$, then $v$ is called a substring of $u$. For example, 'cde' is a substring of 'abcdef'. If $vv$ is a substring of $u$, then $vv$ is called a repeated substring of $u$, where $vv$ denotes the concatenation of string $v$ with itself. For example, when $v=$ 'abc', $vv=$ 'abcabc' is a substring of $u=$ 'cabcabcd', so 'abcabc' is a repeated substring of 'cabcabcd'.

Let us count the number of distinct repeated substrings in a string. For example, in $u=$ 'abcabcbcbc', all repeated substrings of $u$ are listed in the table below: abcabcbcbc abcabcbcbc abcabcbcbc abcabcbcbc

Among these, the distinct repeated substrings are 'abcabc', 'bcbc', and 'cbcb', totaling 3.

We call a string consisting only of the characters 0 and 1 a 01 string. Given the length of a string, we hope you can find a 01 string that contains as few distinct repeated substrings as possible.

Input

This is an answer-submission problem; all input files *.in have already been placed in the problem directory. Each input file contains only a single integer $N$, which specifies the length of the 01 string to be output.

Output

For each input file, you need to provide the corresponding output file in the corresponding directory (the main filename remains the same, with the extension .out). The first line of the output file is an integer representing the number of distinct repeated substrings in the 01 string you found. The second line is a 01 string of length $N$. The output file should not contain any extra characters.

Examples

Input 1

4

Output 1

1
0010

Subtasks

Each test case is scored individually. For each test case, if your output file is invalid (e.g., incorrect file format, the 01 string does not match the first line of the output file, etc.), you will receive 0 points for that test case. Otherwise, let $stdans$ be the number of distinct repeated substrings in the reference output's 01 string, and let $ans$ be your output answer. For different test cases, we have 9 scoring-related constants $a_1 \le a_2 \le a_3 \le a_4 \le a_5 \le a_6 \le a_7 \le a_8 \le a_9$. Your score for the test case is determined by the following statements:

• If $ans > stdans + a_9$, you get 1 point.
• If $ans \le stdans + a_9$, you get 2 points.
• If $ans \le stdans + a_8$, you get 3 points.
• If $ans \le stdans + a_7$, you get 4 points.
• If $ans \le stdans + a_6$, you get 5 points.
• If $ans \le stdans + a_5$, you get 6 points.
• If $ans \le stdans + a_4$, you get 7 points.
• If $ans \le stdans + a_3$, you get 8 points.
• If $ans \le stdans + a_2$, you get 9 points.
• If $ans \le stdans + a_1$, you get 10 points.
• If $ans < stdans$, you get 12 points.

If multiple conditions are met, the highest score is taken as the final score.