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

Ban đầu, tất cả các đĩa được xếp trên cọc bên trái, theo thứ tự tăng dần từ trên xuống dưới (tức là đĩa nhỏ nhất ở trên cùng).

Mục tiêu là di chuyển toàn bộ đĩa sang cọc bên phải, sử dụng cọc giữa làm trung gian.

⚠️ Quy tắc: Mỗi lần, chỉ được di chuyển một đĩa ở trên cùng từ một cọc sang một cọc khác.

Không được đặt đĩa lớn lên trên đĩa nhỏ hơn.

🎯 Nhiệm vụ: Tìm một cách di chuyển các đĩa sao cho:

Số bước di chuyển là ít nhất.

In ra số bước di chuyển, kèm theo danh sách các bước.

Đầu vào:

Dòng duy nhất chứa một số nguyên ~n~: số lượng đĩa.

Đầu ra:

Dòng đầu tiên in một số nguyên ~k~: số bước di chuyển tối thiểu.

Sau đó, in ~k~ dòng, mỗi dòng gồm 2 số nguyên ~a~ và ~b~, biểu diễn một bước: di chuyển đĩa từ cọc ~a~ sang cọc ~b~.

Các cọc được đánh số: 1 = bên trái, 2 = giữa, 3 = bên phải

Ràng buộc:

~1 \le n \le 16~

Ví dụ :

Input:

2

Output:

3
1 2
1 3
2 3