Có ba cọc A, B, C. Ban đầu cọc A có ~n~ đĩa kích thước giảm dần từ dưới lên trên (đĩa lớn nhất ở dưới cùng). Mỗi bước được chuyển một đĩa trên cùng từ cọc này sang cọc khác, nhưng không được đặt đĩa lớn lên đĩa nhỏ. Hãy in ra cách chuyển tất cả các đĩa từ cọc A sang cọc C với số bước ít nhất.

Dữ liệu vào

Một số nguyên dương ~n~ (~1 \le n \le 10~).

Kết quả

Dòng đầu tiên in số bước ~m~ (~m = 2^n - 1~). Mỗi dòng trong ~m~ dòng tiếp theo gồm hai ký tự X Y (cách nhau một dấu cách) nghĩa là chuyển đĩa trên cùng của cọc X sang cọc Y. Cách chuyển với số bước ít nhất là duy nhất.

Ví dụ

Ví dụ 1

Input:

1

Output:

1
A C

Ví dụ 2

Input:

2

Output:

3
A B
A C
B C

Giải thích

Ý tưởng đệ quy: muốn chuyển ~n~ đĩa từ A sang C, ta chuyển ~n - 1~ đĩa từ A sang B (dùng C làm trung gian), chuyển đĩa lớn nhất từ A sang C, rồi chuyển ~n - 1~ đĩa từ B sang C.