Весёлая игра
Группа студентов из n человек собралась, чтобы отметить успешную сдачу экзамена по алгоритмам. Но вот незадача, они забыли купить самое главное для торжества – праздничный торт и теперь нужно выбрать кого-то, кто сходит в магазин за тортом. Так как желающих сделать это добровольно не оказалось, ребята решили сделать выбор с помощью следующей игры.
На плоскости рисуется полный граф из n вершин, пронумерованных от 1 до n, изначально фишка расположена в первой вершине. Каждый игрок должен пройти фишкой по всем вершинам графа, побывав в каждой только один раз и вернуться в начальную позицию, причем каждый путь можно пройти только один раз за игру (разными путями считаются те, в которых различается порядок следования вершин). Тот, кто не сможет построить путь, признается проигравшим и отправляется за тортом. Ребята ходили по очереди и известно, что за тортом отправился игрок, ходивший n-ным. Ваша задача определить какое наименьшее число ребят могло быть в группе, если известно что их было не менее m.
Входные данные
В первой строке входного файла задано количество тестов t (1 ≤ t ≤ 1000). Каждый тест состоит из единственного числа m (1 ≤ m ≤ 10^18).
Выходные данные
Для каждого теста выведите в отдельной строке единственное число, являющееся ответом к задаче.