C2 - Náhrdelník lásky

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≤10⁹

Príklad

Vstup:

2
4
1000

Výstup:

3
11