Trò chơi tháp Hà Nội 2 là trò chơi thay đổi của tháp Hà Nội cổ điển gồm \(n\) đĩa với \(n\) kích thước khác nhau.

Cụ thể: 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;
• Một lần chỉ được di chuyển một đĩa nằm trên cùng từ cọc A sang cọc B, hoặc từ cọc B sang cọc C hoặc từ cọc C sang cọc A;
• Một đĩa chỉ được đặt lên một đĩa không nhỏ hơn.

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\) (\(n \le 15\)).

Output

• Gồm một xâu \(s\) chỉ gồm các kí tự A, B, C trong đó kí tự thứ \(i\) của xâu mô tả bước thứ \(i\) là di chuyển một đĩa từ cọc nào.

Example

1

AB