Tháp Hà Nội (Tower of Hanoi) là một bài toán đố rất nổi tiếng và gắn liền với nhiều câu chuyện thú vị. Bài toán được mô tả như sau: có ba cây cọc được đánh số theo thứ tự \(1,\ 2\) và \(3\). Ban đầu xỏ \(n\) chiếc đĩa vào cây cọc thứ \(1\) sao cho kích thước của các đĩa tăng dần từ trên xuống dưới. Tìm cách để chuyển toàn bộ đĩa sang cọc thứ \(3\) và phải tuân thủ các quy tắc sau:

• Chỉ được di chuyển các đĩa qua \(3\) cọc trên (không được lấy ra ngoài).
• Mỗi lần chỉ được di chuyển một đĩa nằm trên cùng của một cọc nào đó.
• Đĩa có kích thước nhỏ luôn được đặt trên đĩa có kích thước lớn hơn.

Yêu cầu: Tìm cách chơi sử dụng ít bước đi nhất có thể.

Source: Wikipedia

Input

• Gồm một số nguyên dương \(n\) duy nhất: số lượng đĩa.

Output

• Dòng đầu tiên in ra số nguyên dương \(k\): số bước duy chuyển tối ưu;
• Sau đó là \(k\) dòng, mô tả lần lượt các bước di chuyển. Mỗi dòng chứa hai số nguyên \(x\) và \(y\ (1\leq x,\ y\leq3)\), tức là chuyển đĩa trên cùng của cọc \(x\) sang trên cùng cọc \(y\).

Ví dụ

Sample input

2

Sample output

3
1 2
1 3
2 3

Ràng buộc

• \(1\leq n\leq16\).