Alice hefur klifið metorðastigann í mörg ár og loksins náð alla leið á toppinn. Hún er nýorðin forstjóri (CEO) stórs skráðs hlutafélags. Fyrri forstjóri var rekinn vegna slæmrar fjárhagslegrar afkomu, en Alice veit upp á hár hvernig á að auka hagnaðinn. Tími til kominn að velja nýtt nafn á fyrirtækið!

Fjárfestar elska allt sem minnir á gervigreind, sérstaklega í nafni fyrirtækisins. Grunngildi fyrirtækisins jafngildir lengd nafns þess og hvert tilvik hlutstrengsins „AI“ margfaldar gildi fyrirtækisins með 5. Til dæmis hefur nafnið „AAICPCAIIA“ lengdina 10 og tvö (undirstrikuð) tilvik af „AI“:

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

Fleiri dæmi:

• $\operatorname{value}(\texttt{AXI}) = 3$ (núll tilvik af „AI“)
• $\operatorname{value}(\texttt{AIAIAIAI}) = 8 \cdot 5 \cdot 5 \cdot 5 \cdot 5 = 5000$ (fjögur tilvik af „AI“)
• $\operatorname{value}(\texttt{AIMPPZ}) = 6 \cdot 5 = 30$ (eitt tilvik af „AI“)

Samningur Alice tryggir henni einstaklega rausnarlegan bónus ef gildi fyrirtækisins er nákvæmlega $n$. Hún vill líka að nafnið sé eins stutt og mögulegt er.

Alice er nú þegar upptekin við næsta verkefni sitt – að hanna uppfærða merkið. Getur þú lagt til nýtt fyrirtækisnafn á meðan? Finndu stysta mögulega orðið með gildið $n$, sem samanstendur af enskum hástöfum A-Z.

Inntak

Eina línan inniheldur heiltölu $n$ ($1 \le n \le 100\,000$) – óskað gildi fyrirtækisins.

Úttak

Prentaðu orð sem samanstendur af bókstöfunum A-Z – nafn með gildið $n$ og minnstu mögulegu lengd. Ef margar lausnir eru til skal prenta hvaða lausn sem er.

Dæmi

Inntak 1

30

Úttak 1

AIMPPZ

Inntak 2

250

Úttak 2

AAICPCAIIA

Athugasemd

Í fyrsta prófinu leitum við að stysta mögulega nafninu með gildið 30. Bestu orðin hafa lengdina 6 og eitt tilvik af „AI“, til dæmis „AIMPPZ“, „HUAWAI“, „BRAINS“ og „AAAIII“. Ekkert styttra orð hefur gildið 30.

Í öðru prófinu er ekki hægt að ná gildinu 250 með nafni sem er styttra en 10 stafir.