Группа студентов из \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 Для каждого теста выведите в отдельной строке единственное число, являющееся ответом к задаче.