Fișierul intrare/ieșire	lego.in, lego.out	Sursă	Concurs Nerdvana 2022, clasa a 6-a
Autor	Cristian Frâncu | Mihai Tuțu	Adăugată de	Cristian Frâncu • francu
Timp de execuție pe test	0.45 sec	Limită de memorie	8192 KB
Scorul tău	N/A	Dificultate	2

Poți vedea testele pentru această problemă accesând atașamentele .

Vezi soluțiile trimise | Statistici

Lego (clasa a 6-a)

Compania Lego a început să vândă un nou set de piese, având piese de mai multe lungimi numere naturale:

• O singură piesă cu lungimea L, fiind cea mai mare piesă din set.
• Restul pieselor din set au lungimi strict mai mici decât L, dar mai mari ca 1.
• Piesele mai mici decât L au lungimi submultipli ai lui L.
• În set nu există două piese de aceeași lungime.

De exemplu, pentru setul cu piesa cea mai mare L = 32, acesta are în componență alte 4 tipuri diferite de piese, submultipli ai lui L: piese de lungimi 2, 4, 8, și 16.

Fiecare fabrică Lego are o matriță ce poate produce piese de dimensiune maximă L. Deși matrița poate produce piese de lungime 1, pentru siguranța copiilor, Lego nu pune niciodată piese de dimensiunea 1 în seturile sale, de teamă ca acestea să nu fie înghițite accidental.

Cerință

Pentru că vrea să își pregătească fabricile pentru producția noului set de Lego, compania vrea să știe care este dimensiunea cea mai mică a unei piese D ≤ L pe care o poate produce o fabrică astfel încât noul set să aibă cât mai multe piese de lungimi diferite. De exemplu, pentru L = 32 vom alege D = 24, deoarece în setul cu piesa cea mai mare de lungime 24 vom avea alte 6 piese, de lungimi 2, 3, 4, 6, 8 și 12.

Date de intrare

Fișierul de intrare lego.in conține pe prima linie un număr natural L, reprezentând lungimea maximă a unei piese pe care o poate produce fabrica Lego.

Date de ieșire

Fișierul de ieșire lego.out conține pe o singură linie D, lungimea cea mai mică determinată care are număr maxim de tipuri de piese de dimensiuni diferite în set.

Restricții

• 1 ≤ L ≤ 1 000 000

Exemple