Alice a gravi les échelons de l'entreprise pendant de nombreuses années et a finalement atteint le sommet. Elle vient de devenir la directrice générale (PDG) d'une grande entreprise cotée en bourse. Le PDG précédent a été licencié en raison de mauvais résultats financiers, mais Alice sait parfaitement comment stimuler les bénéfices. Il est temps de choisir un nouveau nom d'entreprise !

Les investisseurs adorent toute mention de l'intelligence artificielle, en particulier dans le nom de l'entreprise. La valeur de base de l'entreprise est égale à la longueur de son nom, et chaque occurrence de la sous-chaîne « AI » multiplie la valeur de l'entreprise par 5. Par exemple, le nom « AAICPCAIIA » a une longueur de 10 et deux occurrences (soulignées) de « AI » :

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

Autres exemples :

• $\operatorname{value}(\texttt{AXI}) = 3$ (zéro occurrence de « AI »)
• $\operatorname{value}(\texttt{AIAIAIAI}) = 8 \cdot 5 \cdot 5 \cdot 5 \cdot 5 = 5000$ (quatre occurrences de « AI »)
• $\operatorname{value}(\texttt{AIMPPZ}) = 6 \cdot 5 = 30$ (une occurrence de « AI »)

Le contrat d'Alice lui garantit un bonus exceptionnellement généreux si la valeur de l'entreprise est exactement $n$. Elle souhaite également que le nom soit aussi court que possible.

Alice est déjà occupée par sa prochaine tâche : concevoir le nouveau logo. Pouvez-vous lui proposer un nouveau nom d'entreprise en attendant ? Trouvez le mot le plus court possible de valeur $n$, composé des lettres majuscules anglaises A-Z.

Entrée

La seule ligne contient un entier $n$ ($1 \le n \le 100\,000$) – la valeur souhaitée de l'entreprise.

Sortie

Affichez un mot composé des lettres A-Z – un nom de valeur $n$ et de la plus petite longueur possible. S'il existe plusieurs solutions, affichez l'une d'entre elles.

Exemples

Entrée 1

30

Sortie 1

AIMPPZ

Entrée 2

250

Sortie 2

AAICPCAIIA

Note

Dans le premier test, nous cherchons le nom le plus court possible de valeur 30. Les mots optimaux ont une longueur de 6 et une occurrence de « AI », par exemple « AIMPPZ », « HUAWAI », « BRAINS » et « AAAIII ». Aucun mot plus court n'a une valeur de 30.

Dans le second test, la valeur 250 ne peut pas être atteinte avec un nom de moins de 10 caractères.