Alexandra e pasionată de baze de numeraţie. Ea vrea sa calculeze cifra de control a unui număr în cea mai mică bază de numeraţie în care poate fi reprezentat acel număr. Se numeşte cifră de control a unui număr, cifra care se obţine prin adunări repetate ale cifrelor numărului până obţinem o singură cifră. Exemplu: 1294 în baza 10 are suma cifrelor 16 care adunate din nou dau cifra de control 7. Dar Alexandra are la dispoziţie un număr care poate conţine nu doar cifre, ci şi litere mari ale alfabetului. A înseamnă cifra 10, B cifra 11, ..., Z cifra 35. Deci baza maximă posibilă este 36.
Cerinţă
Dându-se un număr printr-un şir de caractere format doar din litere mari şi cifre, să se determine cea mai mică bază de numeraţie posibilă, precum şi cifra de control a acestui număr în acea bază.
Date de intrare
Fişierul de intrare cifrab.in conţine un şir de caractere format doar din litere mari şi cifre, acest şir reprezentând numărul.
Date de ieşire
Fişierul de ieşire cifrab.out va conţine pe prima linie cea mai mică bază, iar pe a doua linie cifra de control a numărului reprezentat în baza determinată.
Restricţii
Numărul are maximum 100 000 de cifre
Baza este cuprinsă între 2 şi 36
Exemplu
cifrab.in
cifrab.out
Explicaţii
349
10
7
Cea mai mică bază este 10
Calculând cifra de control în baza 10 se obţin pe rând valorile 349, 16, 7
cifrab.in
cifrab.out
Explicaţii
ABF27
16
F
Cea mai mică bază este 16.
Calculând cifra de control în baza 16 se obţin pe rând valorile ABF27, 2D, F