Trò chơi tháp Hà nội gồm \(n\) đĩa với \(n\) kích thước khác nhau và \(4\) cọc \(A, B, C, D\).

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

• Chỉ sử dụng \(4\) cọc để chuyển;
• 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 có kích thước lớn hơn.

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

Input

• Gồm một dòng duy nhất 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.

Example

3

5
AB
AC
AD
CD
BD

Ràng buộc

• Subtask \(1\) (\(20\%\) số điểm): \(n \leq 5\)
• Subtask \(2\) (\(24\%\) số điểm): \(n \leq 20\)
• Subtask \(3\) (\(28\%\) số điểm): \(n \leq 40\)
• Subtask \(4\) (\(28\%\) số điểm): \(n \leq 100\)