Matematicianul Albert Wilansky avea numărul de telefon a cumnatului său, Harold Smith. Numărul cu pricina era 4937775. Până aici nimic deosebit, numai că matematicianul a constat un lucru extrem de curios: în primul rând a calculat suma cifrelor S şi a obţinut valoarea:
S(4937775) = 4+9+3+7+7+7+5 = 42
Apoi a descompus numărul în factori primi şi a obţinut:
4937775 = 3*5*5*65837  
şi făcând suma cifrelor factorilor Sp a obţinut tot 42:
Sp(4937775) = Sp(3*5*5*65837) = 3+5+5+(6+5+8+3+7) = 42

Cerinţă

Gigel, mare amator de probleme cu numere, şi-a pus câteva probleme. Dacă se cunoaşte n, numărul de cifre, care este:
a. cel mai mare număr Smith cu n cifre (2<=n<=7)
b. cel mai mare număr Smith palindrom cu n cifre (2<=n<=8)
c. cel mai mare număr Smith cu n cifre care are proprietatea că şi inversul său este tot număr Smith, fără a fi palindrom (2<=n<=5)
d. cel mai mare număr Smith cu n cifre care este pătrat perfect (2<=n<=9)

Date de intrare

De pe prima linie a fişierului de intrare smith.in se citeşte un caracter care poate avea doar valorile 'a', 'b', 'c' sau 'd' indicând una dintre cele 4 cerinţe posibile ale lui Gigel. De pe linia a doua a fişierului de intrare se citeşte valoarea n reprezentând numărul de cifre ale numărului cerut.

Date de ieşire

Pe prima linie a fişierului de ieşire smith.out se va afişa o singura linie ce contine numărul maxS cerut. În cazul în care nu există numere Smith cu n cifre cu proprietatea cerută se va afişa valoarea 0.

Restricţii

• 2 <= n <= 7 (pentru cerinţa a)
• 2 <= n <= 8 (pentru cerinţa b)
• 2 <= n <= 5 (pentru cerinţa c)
• 2 <= n <= 9 (pentru cerinţa d)

Exemplu