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