Весела гра#3240

Весела гра

5 секунд
256 мегабайтів
Легка

Група студентів із осіб зібралася, щоб відсвяткувати успішно складений іспит з алгоритмів. Але вони забули купити найважливіше для святкування — святковий торт, і тепер потрібно обрати когось, хто піде в магазин за тортом. Оскільки охочих зробити це добровільно не знайшлося, вони вирішили вибрати з допомогою наступної гри.

На площині малюється повний граф з вершинами, пронумерованими від до , початково фішка знаходиться у вершині під номером один. Кожен гравець повинен провести фішку по всіх вершинах графа, відвідавши кожну лише один раз і повернувшись у вихідну позицію, кожен шлях може бути використаний лише один раз за гру (різними вважаються маршрути, що відрізняються порядком проходження вершин). Той, хто не зможе побудувати шлях, вважається вибраним грою й іде за тортом. Студенти ходили по черзі, і відомо, що за тортом пішов гравець, який ходив -им. Ваше завдання — визначити, якою могла бути найменша кількість студентів у групі, якщо відомо, що їх було не менше, ніж .

Вхідні дані

У першому рядку вхідного файлу зазначено кількість тестів (1 \le t \le 1000). Кожен тест складається з одного числа (1 \le m \le 10^{18}).

Вихідні дані

Для кожного тесту виведіть у єдиному рядку одне число — відповідь на задачу.

Приклади

Приклад 1

Loading
Loading