factfact

Într-un laborator secret de matematică, elevii au descoperit o categorie bizară de numere pe care le-au numit factfact. Pentru a înțelege aceste numere, profesorii au reamintit mai întâi definiția factorialului: pentru un număr natural $n \geq 1$, factorialul său, notat $n!$ reprezintă produsul numerelor naturale de la $1$ la $n$ (spre exemplu $4!=1⋅2⋅3⋅4=24$). Un număr se numește factfact dacă se poate obține prin concatenarea (lipirea cifrelor) a exact două valori factoriale. De exemplu, numărul $12024$ este factfact, deoarece se poate scrie ca $5!$ concatenat cu $4!$ adică $120$ urmat de $24$. În schimb, numărul $123$ nu este factfact, deoarece nu există două factoriale ale unor numere naturale care, concatenate, să formeze această valoare. Profesorii au observat că astfel de coduri apar frecvent în bazele de date ale școlii, iar analiza lor a devenit esențială pentru arhivare și securitate. Dorel, pasionat de algoritmi, a primit sarcina de a identifica rapid aceste numere speciale, de a le compara și de a analiza secvențele în care apar, pentru a optimiza sistemul informatic al laboratorului. În primă fază, Dorel ar vrea să afle dacă un număr dat este factfact sau nu. Apoi, dându-se numerele din baza de date a școlii, ar vrea să afle numărul factfact cu valoare maximă dintre acestea. Din motive de securitate, el trebuie să afle care este cea mai lungă secvență de numere factfact care să conțină obligatoriu cel mai mare număr factfact dintre toate.

Cerință

• Determinați dacă un număr este factfact sau nu.
• Dându-se mai multe numere, determinați cel mai mare număr factfact dintre ele.
• Dându-se mai multe numere, determinați cea mai lungă secvență de numere factfact care să conțină obligatoriu cel mai mare număr factfact dintre toate.

Date de intrare

Pe prima linie a fișierului de intrare factfact.in se găsește $C$ reprezentând cerința.

• Dacă $C=1$, pe cea de-a doua linie se va afla un singur număr natural $x$ cu semnificația din enunț.
• Dacă $C=2$ sau $C=3$, pe cea de-a doua linie se va un număr natural $N$. Pe următoarea linie se vor afla $N$ numere naturale $v_1,v_2,...,v_N$, separate prin câte un spațiu.

Date de ieșire

Pe prima linie a fișierului de ieșire factfact.out se va găsi un singur număr întreg, după cum urmează:

• Dacă $C=1$, se va afișa $1$ dacă numărul dat este factfact, iar $0$ în caz contrar.
• Dacă $C=2$, se va afișa cel mai mare număr factfact dintre cele date.
• Dacă $C=3$, se va afișa lungimea secvenței cerute.

Restricții și precizări

• Se garantează că pentru $C=2$ și $C=3$ există cel puțin un număr factfact în șir.
• În formarea numărului factfact, cele două numere nu pot avea $0$-uri nesemnificative (vezi exemplul $1$)
• $1 \leq N \leq 100 \ 000$;
• $1 \leq v_i,x \leq 10^9$

Exemplul 1

factfact.in

1 
101

factfact.out

0

Explicație

Deși $101$ poate fi format prin concatenarea lui $1$ cu $01$, $01$ are un $0$ nesemnificativ și nu se consideră un număr corect matematic.

Exemplul 2

factfact.in

2 
10 
100000 11 12 16 26 107 24120 108 24120 22

factfact.out

24120

Explicație

Cel mai mare număr factfact este $24120$.

Exemplul 3

factfact.in

3 
10 
100000 11 12 16 26 107 24120 108 24120 22

factfact.out

2

Explicație

Cea mai lungă secvență formată doar din numere factfact care îl conțină pe $24120$ este formată din ultimele $2$ numere.