Viết chương trình ghi tất cả các dãy số sắp xếp theo thứ tự từ điển được tạo thành từ các số $1, 2, 3$. Các dãy số không có 2 đoạn con liên tiếp nào giống nhau và độ dài mỗi dãy không vượt quá $n$.

Dữ liệu vào

• Số nguyên dương $n$ $(1≤n≤30)$

Kết quả

• Mỗi dãy được ghi trên một dòng, các số trên một dòng được viết liên tiếp nhau

Ví dụ:

Input

2 

Output

1
12
13
2
21
23
3
31
32