Giáng Sinh sắp đến gần, trưởng thôn Minh quyết định chuẩn bị tổ chức một buổi tặng quà đặc biệt cho \(N\) bạn coder trong thôn. Các bạn sẽ ngồi thành một vòng tròn để nhận quà từ trưởng thôn Minh. Tuy nhiên, Minh muốn đảm bảo rằng không có hai bạn ngồi cạnh nhau nhận được cùng một món quà giống nhau, để tránh các bạn ganh tị hoặc chia sẻ quà.

Ban đầu, trưởng thôn Minh chuẩn bị \(N\) món quà khác nhau được đánh dấu bằng các chữ cái từ \(A, B, C, D, \ldots\) Minh nhận ra rằng với \(N\) bạn coder và \(N\) loại quà khác nhau, mỗi bạn coder không chỉ có thể nhận một món quà mà còn có thể nhận nhiều món quà, miễn là tất cả các quy tắc sau đây được đảm bảo:

• Mỗi bạn coder đều nhận được số lượng quà giống nhau.
• Mỗi món quà xuất hiện với số lần bằng nhau.
• Không có hai bạn coder ngồi cạnh nhau nhận được cùng một món quà giống nhau.
• Có \(N\) loại quà khác nhau có thể dùng, được đánh dấu bởi \(N\) chữ cái in hoa đầu tiên từ \(A\) đến \(Z\)
• Mỗi bạn coder có thể nhận tối đa 1 món quà cho mỗi loại quà từ \(1\) đến \(N\)

Với tư cách là trợ lý trưởng thôn, bạn hãy giúp trưởng thôn Minh tìm ra số lượng quà tối đa mà mỗi bạn coder có thể nhận, đồng thời đưa ra cách phân phối quà để đảm bảo các quy tắc trên.

Input

• Dữ liệu vào gồm một dòng duy nhất chứa số nguyên \(N\) \((1 \leq N \leq 26)\) là số lượng bạn coder (cũng là số lượng món quà ban đầu).

Output

• Dòng đầu tiên in ra một số nguyên \(1 \leq M \leq N\), là số lượng quà tối đa mà mỗi bạn có thể nhận.
• In ra \(N\) dòng tiếp theo, mỗi dòng chứa \(M\) chữ cái viết hoa, biểu thị các món quà mà bạn nhỏ thứ \(i\) nhận được. Mỗi chữ cái phải nằm trong \(N\) chữ cái viết hoa đầu tiên trong bảng chữ cái từ \(A\) đến \(Z\). Đảm bảo các món quà được phân phối thỏa mãn cả ba quy tắc. Nếu có nhiều cách in thỏa mãn, in ra một cách bất kì.

Example

1

1
A

2

1
B
A

4

2
DA
BC
AD
CB