divizor

Se consideră un număr natural $N$ format din $m$ cifre și toate cele $m - 1$ numere ce se pot forma succesiv pornind de la numărul inițial $N$, prin mutarea celei mai semnificative cifre a combinației curente la sfârșitul acesteia, după cum se poate observa din exemplele de mai jos.

$N = 12035 \rightarrow 20351 \rightarrow 03512 \rightarrow 35120 \rightarrow 51203$ ($4$ combinații). Se taie zeroul de la inceputul lui $03512$ iar numărul a rămas $3512$.

$N = 2121 \rightarrow 1212 \rightarrow 2121 \rightarrow 1212$ ($3$ combinații, $3$ numere)

Cerință

Scrieți un program care să citească numărul $N$, să construiască cele $m - 1$ numere și să determine:

1. numărul cu cel mai mare număr de divizori, dintre cele $m$ numere; dacă sunt mai multe astfel de numere printre cele $m$, se vor scrie în fișierul de ieșire toate aceste numere.
2. cel mai mare număr care este divizor propriu pentru cel puțin unul din cele $m$ numere, iar în cazul în care nu există un astfel de divizor (toate cele $m$ numere sunt prime), se va afișa valoarea $0$.

Date de intrare

Fișierul divizor.in conține o singură linie pe care este scris numărul natural $N$.

Date de ieșire

Fișierul divizor.out va conține:

• pe prima linie numărul sau numerele cu număr maxim de divizori, despărțite prin câte un spațiu
• pe a doua linie, un număr natural reprezentând cel mai mare număr care este divizor propriu pentru cel puțin unul din cele $m$ numere sau $0$, în cazul în care toate cele $m$ numere sunt numere prime

Restricții și precizări

• $1 \leq N < 1 \ 000 \ 000$;
• Conform procedurii de formare a combinațiilor, se poate întâmpla să se obțină de mai multe ori același număr. Se vor considera toate combinațiile posibile, chiar dacă există numere care se repetă.
• Cifra $0$ scrisă în fața unui număr se consideră neglijabilă și nu se cere afișată în rezultatul final.
• La toate cerințele se ia în considerare și numărul inițial.
• Divizorul propriu al unui număr este un divizor diferit de $1$ și de număr.
• Se acordă punctaje parțiale: cerința a) 60% din punctaj, cerința b) 40% din punctaj

Exemplu

divizor.in

212

divizor.out

212
106

Explicație

Numerele obținute: $212$ (inițial), $122$, $221$. $212$ are $6$ divizori, $122$ și $221$ au câte $4$ divizori. Deci numărul cu cel mai mare număr de divizori este $212$. Cel mai mare divizor propriu este $106$ (divizorul numărului $212$) .