Prihlásenie Registrácia  

C1 - Náhrdelník lásky

Časový limit: 2s, Pamäťový limit: 64MiB

Programovacie jazyky: Pascal, C, C++, Java, C++0x, Python 3

Počet bodov: 1

[ Pošli riešenie ] [ Tvoje riešenia ] [ Správne riešenia ] [ Vzorové riešenie ]

Pocahontas pripravuje pre Johna Smitha náhrdelník lásky. Náhrdelník má obsahovať N korálikov, z ktorých každý bude zafarbený nejakým odtieňom ružovej farby. Pocahontas však vie, že v pravom náhrdelníku lásky nemôžu byť koráliky zafarbené len tak ledabolo – medzi každými dvoma korálikmi, ktoré sú zafarbené tým istým odtieňom ružovej farby, musí byť aspoň jeden korálik, ktorý je zafarbený nejakým tmavším odtieňom (tmavší korálik musí byť na obidvoch cestách medzi nimi, teda v smere aj proti smeru hodinových ručičiek). Pomôžte Pocahontas zistiť, koľko najmenej odtieňov ružovej farby musí použiť!

Vstup

Prvý riadok vstupu obsahuje kladné celé číslo Q, (1≤Q≤1000), určujúce počet testovacích sád. Každý z nasledujúcich Q riadkov obsahuje jedno kladné celé číslo N – počet korálikov.

Výstup

Pre každú testovaciu sadu vypíšte jediný riadok obsahujúci jedno kladné celé číslo – najmenší možný počet odtieňov ružovej potrebný na výrobu náhrdelníka lásky s N korálikmi.

C1

3≤N≤10

C2

3≤N≤109

Príklad

Vstup:

2
4
1000

Výstup:

3
11