Alice has climbed the corporate ladder for many years and finally reached the very top. She has just become the Chief Executive Officer (CEO) of a large publicly traded company. The previous CEO was fired due to poor financial results, but Alice knows perfectly well how to boost profits. Time to choose a new company name!

Investors love any mention of artificial intelligence, especially in the company name. The base value of the company equals the length of its name, and each occurrence of the substring "AI" multiplies the company's value by 5. For example, the name "AAICPCAIIA" has length 10 and two (underlined) occurrences of "AI":

• $\operatorname{value}(\texttt{AAICPCAIIA}) = 10 \cdot 5 \cdot 5 = 250$

More examples:

• $\operatorname{value}(\texttt{AXI}) = 3$ (zero occurrences of "AI")
• $\operatorname{value}(\texttt{AIAIAIAI}) = 8 \cdot 5 \cdot 5 \cdot 5 \cdot 5 = 5000$ (four occurrences of "AI")
• $\operatorname{value}(\texttt{AIMPPZ}) = 6 \cdot 5 = 30$ (one occurrence of "AI")

Alice's contract guarantees her an exceptionally generous bonus if the company's value is exactly $n$. She also wants the name to be as short as possible.

Alice is already busy with her next task – designing the refreshed logo. Can you propose a new company name in the meantime? Find the shortest possible word of value $n$, consisting of uppercase English letters A-Z.

Input

The only line contains an integer $n$ ($1 \le n \le 100\,000$) – the desired company value.

Output

Print a word consisting of the letters A-Z – a name with value $n$ and the smallest possible length. If many solutions exist, output any of them.

Examples

Input 1

30

Output 1

AIMPPZ

Input 2

250

Output 2

AAICPCAIIA

Note

In the first test, we look for the shortest possible name of value 30. Optimal words have length 6 and one occurrence of "AI", for example "AIMPPZ", "HUAWAI", "BRAINS" and "AAAIII". No shorter word has value 30.

In the second test, value 250 cannot be achieved with a name shorter than 10 characters.