Група з \textbf{n} студентів зібралась, щоб відмітити успішну здачу екзамену по алгоритмам. Але ось незадача, вони забули придбати саме головне для святкування -- святковий торт, і тепер потрібно вибрати когось, хто сходить у магазин за тортом. Так як бажаючих зробити це добровільно не виявилось, вони вирішили зробити вибір при допомозі наступної гри. На площині зображається повний граф з \textbf{n} вершин, пронумерованих від \textbf{1} до \textbf{n}, на початку гри фішку розміщено у першій вершині. Кожен гравець повинен пройти фішкою по усім вершинам графа, побувавши у кожній лише один раз і повернутись у початкову позицію, причому кожним шляхом можна пройти лише один раз за гру (різними шляхами вважається ті, у яких відрізняється порядок слідування вершин). Той, хто не зможе побудувати шлях, признається програвшим і відправляється за тортом. Студенти ходили по черзі і відомо, що за тортом відправився гравець, який ходив \textbf{n}-им. Ваша задача визначити яка нйименша кіькість студнтів могла бути у групі, якщо відомо, що їх було не менше \textbf{m}. \InputFile У першому рядкуе вхідного файлу задано кількість тестів \textbf{t} (\textbf{1} ≤ \textbf{t} ≤ \textbf{1000}). Кожен тест складається з єдиного числа \textbf{m} (\textbf{1} ≤ \textbf{m} ≤ \textbf{10^18}). \OutputFile Для кожного тесту виведіть у окремому рядку єдине число, яке є відповіддю до задачі.