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