Tháp Hà Nội

Nguồn: CSES Problem Set

Phiên bản: Phước Hưng OJ Extended

Đề bài

Trò chơi Tháp Hà Nội gồm ba cọc: cọc trái, cọc giữa và cọc phải, cùng với $n$ đĩa tròn có kích thước đôi một khác nhau.

Ban đầu, tất cả các đĩa đều nằm trên cọc trái và được xếp theo thứ tự kích thước tăng dần từ trên xuống dưới: đĩa nhỏ nhất ở trên cùng và đĩa lớn nhất ở dưới cùng.

Mục tiêu là chuyển toàn bộ $n$ đĩa từ cọc trái sang cọc phải, với cọc giữa được sử dụng làm cọc trung gian.

Trong mỗi bước di chuyển:

• chỉ được lấy đĩa nằm trên cùng của một cọc;
• đĩa được lấy ra phải được đặt lên trên cùng của một cọc khác;
• không được đặt một đĩa lớn hơn lên trên một đĩa nhỏ hơn.

Hãy tìm một dãy thao tác hợp lệ sao cho tổng số bước di chuyển là nhỏ nhất.

Ba cọc được đánh số lần lượt như sau:

• cọc trái là cọc $1$;
• cọc giữa là cọc $2$;
• cọc phải là cọc $3$.

Input

Dòng duy nhất chứa số nguyên $n$ — số lượng đĩa.

Output

Dòng đầu tiên in ra số nguyên $k$ — số bước di chuyển nhỏ nhất cần thực hiện.

Tiếp theo, in ra $k$ dòng mô tả các bước di chuyển theo đúng thứ tự thực hiện.

Mỗi dòng chứa hai số nguyên $a$ và $b$, biểu thị việc chuyển đĩa trên cùng từ cọc $a$ sang cọc $b$.

Subtask

• Subtask 1 — 100%: $1 \le n \le 16$.

Ví dụ

Input

2

Output

3
1 2
1 3
2 3

Giải thích

Có $2$ đĩa ban đầu đều nằm trên cọc $1$.

Trước tiên, chuyển đĩa nhỏ từ cọc $1$ sang cọc $2$:

1 2

Sau đó, đĩa lớn có thể được chuyển từ cọc $1$ sang cọc $3$:

1 3

Cuối cùng, chuyển đĩa nhỏ từ cọc $2$ sang cọc $3$:

2 3

Sau $3$ bước, cả hai đĩa đều nằm trên cọc $3$ và mọi thao tác đều tuân thủ quy tắc không đặt đĩa lớn hơn lên trên đĩa nhỏ hơn.

Không thể hoàn thành việc chuyển hai đĩa với ít hơn $3$ bước, vì vậy kết quả trên đạt số bước di chuyển nhỏ nhất.