Trò chơi tháp Hà Nội 1 là trò chơi biến thể của tháp Hà Nội gồm \(2n\) đĩa với \(n\) kích thước khác nhau (mỗi kích thước đĩa có đúng hai cái đĩa).

Trò chơi bắt đầu bằng trạng thái các đĩa được chồng lên nhau ở cọc \(A\). Yêu cầu của trò chơi là chuyển toàn bộ số đĩa từ cọc \(A\) sang cọc \(C\), tuân theo các quy tắc sau:

• Chỉ sử dụng 3 cọc để chuyển (\(A, B, C\));
• Một lần chỉ được di chuyển một đĩa nằm trên cùng từ cọc này sang cọc khác;
• Một đĩa chỉ được đặt lên một đĩa không nhỏ hơn (đĩa có cùng kích thước được phép đặt lên nhau).

Yêu cầu: Hãy tìm cách chuyển toàn bộ đĩa thành một chồng đĩa ở cọc \(C\).

Input

• Dòng đầu chứa số nguyên dương \(n\).

Output

• Dòng đầu chứa số nguyên \(s\) là số lần chuyển đĩa;
• Dòng thứ \(j\) (\(j = 1, 2, \dots, s\)) trong \(s\) dòng tiếp theo, mỗi dòng gồm đúng hai kí tự mô tả một thao tác chuyển đĩa. Cụ thể, kí tự thứ nhất là tên cọc chứa đĩa cần chuyển, kí tự thứ hai là tên cọc mà đĩa chuyển tới.

Constraints

• \(1 \le n \le 10\).

Example

1

2
AC
AC