Yêu cầu:

Hãy liệt kê các xâu độ dài n chỉ gồm hai kí tự ′A′ hoặc ′B′ mà không có hai kí tự ′B′ nào đứng cạnh nhau.

Dữ liệu:

Một dòng ghi số nguyên \(n (n≤20)\).

Kết quả:

In ra các xâu ký tự theo thứ tự từ điển.

Input

3

Output

AAA
AAB
ABA
BAA
BAB