POLSKI SPOJ

Za górami, za lasami, za siedmioma rzekami leżał gród dumny i szlachetny, pełen ludzi pięknych i mądrych. Wiele cudownych historii można by opowiedzieć o nim, lecz Tobie drogi czytelniku niech wystarczy, że jedną z chlub jego była szkoła doprawdy niezwykła - Akademia Pana i Kleksa. Jak co roku, na początku października, strumień nowych adeptów sztuk magicznych przepływał przez mury tejże zacnej instytucji. A wśród nich on - Maciuś. Na pierwszym wykładzie z WDP (Wstęp Do Pascala) Maciuś słuchał z zaciekawieniem i notował pilnie. Niestety, prawa Murphy'ego dały o sobie znać i tym razem. Maciuś usłyszał wszystko ... oprócz rzeczy najważniejszej: hasła do WTF (Wielce Tajnego Forum). Fragment wykładu, w którym profesor mówił o owym haśle, brzmiał mniej więcej tak:

"(...) Pamiętajcie, żeby zalogować się na Wielce Tajne Forum. Hasło do niego to taka najmniejsza liczba, której suma <szum>...ch potęg cyfr modulo 18446744073709551616 jest równa tej liczbie (...)"

Maciuś stanął przed niezwykle trudnym zadaniem. Nie ma on pojęcia o jaką potęgę chodziło. Jak zapewne się domyślasz, Ty jako doświadczony i wielce dobry programista musisz pomóc Maciusiowi i napisać dla niego program, który wczyta różne, dostarczone przez studenta potęgi i dla każdej z nich znajdzie liczbę spełniającą opis profesora. Wtedy on spróbuje się zalogować używając wygenerowanych przez Ciebie liczb. Któraś z nich musi być szukanym hasłem.

Wejście

Na wejściu pojawi się skończona liczba liczb z przedziału [2; 10000], każda w oddzielnej linii. I-ta liczba na wejściu oznacza wykładnik (q) potęgi jaki używamy do obliczania sumy cyfr. Tzn. gdy q = 2, to suma cyfr^q liczby 123 będzie miała postać 1^2 + 2^2 + 3^2 = 14. 

Wyjście

W i-tym wierszu wyjścia należy wypisać odpowiedź na i-te zapytanie. Odpowiedzią jest najmniejsza liczba naturalna większa od 1, spełniająca opis profesora.

Przykład

Wejście:
3
5

Wyjście:

153
4150