Zadanie

Fakt veľa topingov

Počet bodov: 50

Jano našiel veľa pudingu. Veľmi veľa. Naozaj veľmi veľa. Tak veľa, že by sa ho za pár dní prejedol. Našťastie si však môže kúpiť topingy. Fakt veľa topingov. Skutočne neskutočné množstvo topingov. Pomocou veľa rôznych topingov zaistí, že sa nepreje veľa rovnakého pudingu. Čoho ale Jano veľa nemá, sú financie. Koľko najmenej topingov si môže Jano kúpiť, aby sa neprejedol pudingu?

Úloha

Jano má puding na \(n\) dní. Každý deň chce použiť rôznu sadu topingov. Presnejšie, pre každú dvojicu rôznych dní \(i\), \(j\) musí platiť, že v deň \(i\) si dá nejaký toping, ktorý si v deň \(j\) nedá a v deň \(j\) si dá nejaký toping, ktorý si nedá v deň \(i\).

Keďže Jano už dlho neriešil Zenit, zabudol rozmýšľať. Zachránite ho a poviete mu, koľko najmenej topingov si potrebuje kúpiť?

Vstup a Výstup

V prvom riadku vstupu je číslo \(t\) – počet testovacích vstupov.

Nasleduje \(t\) riadkov. Na \(i\)-tom z nich je číslo \(n_i\) – počet dní, koľko Janovi vydrží puding v \(i\)-tom testovacom vstupe.

Pre každý testovací vstup vypíšte 1 riadok. Konkrétne, pre každé \(n_i\) vypíšte odpoveď na otázku: “Koľko najmenej topingov si musí Jano kúpiť, aby si mohol počas každého z \(n_i\) dní dať na puding rôznu sadu topingov?” Pozor! To, ako je definovaná rôznosť sady topingov je bližšie popísané v časti Úloha.

Sú štyri sady vstupov. V prvej platí \(1 \leq n \leq 10\). V druhej platí \(1 \leq n \leq 100\,000\). Vo zvyšných sadách platí \(1 \leq n \leq 10^{18}\).

Vo všetkých sadách platí \(1 \leq t \leq 10\,000\).

Príklad

Input:

3
4
1
2

Output:

4
1
2

Ak má Janovi puding vydržať puding 4 dni, potrebuje aspoň 4 topingy. Jedno z možných použití topingov je nasledovné: {1, 2}, {1, 3}, {1, 4}, {2, 3}. Iné vhodné použitie by bolo {1}, {2}, {3}, {4}