Tháp Hà Nội

Có ba cọc (đánh số 1, 2, 3) và $n$ chiếc đĩa có kích thước khác nhau. Ban đầu, tất cả các đĩa được xếp trên cọc 1 theo thứ tự từ lớn đến nhỏ (đĩa lớn ở dưới, đĩa nhỏ ở trên). Mục tiêu là chuyển toàn bộ đĩa sang cọc 3.

Quy tắc:

• Mỗi lần chỉ được di chuyển một đĩa (đĩa trên cùng của một cọc).
• Không được đặt đĩa lớn lên trên đĩa nhỏ hơn.

Hãy tìm cách di chuyển với số bước ít nhất.

Dữ liệu vào

Một dòng duy nhất chứa số nguyên $n$.

Dữ liệu ra

Dòng đầu tiên in ra $k$ — số bước di chuyển tối thiểu.

• $k$ dòng tiếp theo, mỗi dòng gồm hai số nguyên $a$ và $b$: di chuyển đĩa trên cùng từ cọc $a$ sang cọc $b$.

Ràng buộc

• $1\le n\le 16$

Ví dụ