Cho số nguyên dương ~n~ (~n~ ≤ 20). Hãy liệt kê tất cả các xâu có độ dài ~n~ chỉ chứa hai ký tự ‘A’ hoặc ‘B’ mà trong xâu không có hai ký tự ‘B’ đứng liền nhau. Dữ liệu vào: Chỉ ghi số nguyên dương ~n~. Kết quả: Ghi mỗi dòng một xâu ký tự thỏa mãn điều kiện bài toán và được sắp xếp tăng dần.

Ví dụ

Input

3

Output

AAA
AAB
ABA
BAA
BAB