Tháp Hà Nội là một trò chơi kinh điển giúp tăng cường tư duy, kĩ năng và trí nhớ. Trò chơi gồm ~3~ cột được đánh số từ ~1~ đến ~3~ từ trái qua phải, ban đầu ở cột thứ nhất có ~n~ đĩa sắp xếp nhỏ dần từ dưới lên trên, mỗi lần di chuyển bạn chỉ được di chuyển một đĩa nằm trên cùng của một cột bất kí sang một cột khác, đồng thời đảm bảo sau mỗi bước di chuyển, các đĩa nằm trên luôn nhỏ hơn đĩa nằm dưới nó. Hãy viết chương trình thể hiện cách di chuyển tất cả ~n~ đĩa từ cột ~1~ sang cột ~3~ tốn ít số bước nhất.

Input

Gồm một số nguyên duy nhất ~n~ (~1 \le n \le 20~)

Output

Gồm nhiều dòng, dòng thứ ~i~ chứa ~2~ số nguyên ~s, t~ thể hiện phép di chuyển một đĩa từ cột ~s~ sang cột ~t~ ở bước thứ ~i~.

Sample input

3

Sample output

1 3
1 2
3 2
1 3
2 1
2 3
1 3