Alice har klättrat på karriärstegen i många år och äntligen nått allra högst upp. Hon har precis blivit verkställande direktör (VD) för ett stort börsnoterat företag. Den tidigare VD:n fick sparken på grund av dåliga finansiella resultat, men Alice vet mycket väl hur man ökar vinsten. Dags att välja ett nytt företagsnamn!
Investerare älskar varje omnämnande av artificiell intelligens, särskilt i företagsnamnet. Företagets basvärde är lika med längden på dess namn, och varje förekomst av delsträngen "AI" multiplicerar företagets värde med 5. Till exempel har namnet "AAICPCAIIA" längden 10 och två (understrukna) förekomster av "AI":
- $\operatorname{value}(\texttt{AAICPCAIIA}) = 10 \cdot 5 \cdot 5 = 250$
Fler exempel:
- $\operatorname{value}(\texttt{AXI}) = 3$ (noll förekomster av "
AI") - $\operatorname{value}(\texttt{AIAIAIAI}) = 8 \cdot 5 \cdot 5 \cdot 5 \cdot 5 = 5000$ (fyra förekomster av "
AI") - $\operatorname{value}(\texttt{AIMPPZ}) = 6 \cdot 5 = 30$ (en förekomst av "
AI")
Alices kontrakt garanterar henne en exceptionellt generös bonus om företagets värde är exakt $n$. Hon vill också att namnet ska vara så kort som möjligt.
Alice är redan upptagen med sin nästa uppgift – att designa den uppdaterade logotypen. Kan du föreslå ett nytt företagsnamn under tiden? Hitta det kortaste möjliga ordet med värde $n$, bestående av stora engelska bokstäver A-Z.
Indata
Den enda raden innehåller ett heltal $n$ ($1 \le n \le 100\,000$) – det önskade företagsvärdet.
Utdata
Skriv ut ett ord bestående av bokstäverna A-Z – ett namn med värde $n$ och minsta möjliga längd. Om det finns många lösningar, skriv ut vilken som helst av dem.
Exempel
Indata 1
30
Utdata 1
AIMPPZ
Indata 2
250
Utdata 2
AAICPCAIIA
Anmärkning
I det första testet letar vi efter det kortaste möjliga namnet med värde 30. Optimala ord har längden 6 och en förekomst av "AI", till exempel "AIMPPZ", "HUAWAI", "BRAINS" och "AAAIII". Inget kortare ord har värde 30.
I det andra testet kan värdet 250 inte uppnås med ett namn som är kortare än 10 tecken.