Nhập vào số nguyên dương \(n\) \((0 < n < 15)\). Sinh các dãy nhị phân có độ dài \(n\) không chứa \(101\).

Input

Số nguyên duy nhất \(n\)

Output

Mỗi dòng một dãy nhị phân thỏa mãn đề bài được liệt kê theo thứ tự từ điển.

Example

Input:

3

Output:

000
001
010
011
100
110
111