Tháp Hà Nội

Có ba cột đánh số \(1, 2, 3\). Cột \(1\) có \(n\) đĩa kích thước khác nhau, đĩa lớn ở dưới, đĩa nhỏ ở trên. Cần chuyển toàn bộ \(n\) đĩa sang cột \(3\) theo luật:

• Mỗi lần chỉ được chuyển một đĩa ở trên cùng của một cột sang một cột khác.
• Không bao giờ được đặt đĩa lớn lên trên đĩa nhỏ hơn.

Hãy in ra cách chuyển với ít bước nhất (cách chuyển ít bước nhất là duy nhất).

Input

• Một số nguyên dương \(n\) (\(1 \le n \le 15\)).

Output

• Dòng đầu tiên là số bước chuyển ít nhất \(k\).
• \(k\) dòng tiếp theo, mỗi dòng gồm hai số \(x\ y\), nghĩa là chuyển đĩa trên cùng của cột \(x\) sang cột \(y\).

Sample Input 1

2

Sample Output 1

3
1 2
1 3
2 3