Вы участвуете в гонках на \textbf{2D} решетке, стартуя с начала координат (\textbf{0}, \textbf{0}) и двигаетесь к финишу (\textbf{M}, \textbf{N}), где \textbf{М} и \textbf{N} - натуральные числа, \textbf{0} < \textbf{M} ≤ \textbf{N}. На пути имеется контрольная точка, которая не совпадает ни с точкой старта, ни с точкой финиша. Она имеет координаты (\textbf{m}, \textbf{n}), причем \textbf{0} ≤ \textbf{m} ≤ \textbf{M} и \textbf{0} ≤ \textbf{n} ≤ \textbf{N}. Вам следует пройти контрольную точку прежде, чем достигните финиша. Длина самого короткого пути до финиша равна \textbf{T} = \textbf{M} + \textbf{N}. Из каждой точки Вы можете перейти в одну из четырех ближайших соседних точек, сохраняя при этом постоянную скорость. Но поскольку Вы не хотите проиграть гонку, то каждый раз продолжать движение будете или вправо, или вверх. Хотя существует много способов дойти до финиша через контрольную точку, гонка является простой, так как найти самый короткий маршрут всегда легко. Для того чтобы сделать гонку более интересной, мы изменим правила. Вместо того чтобы просто двигаться к финишу (\textbf{M}, \textbf{N}), гонщикам предлагается самостоятельно выбрать координаты финиша (\textbf{x}, \textbf{y}) и контрольной точки таким образом, чтобы до финиша существовало ровно \textbf{S} различных кратчайших путей. Например, рассмотрим для \textbf{S = 4} два варианта расположения финиша и контрольной точки. Расположим контрольную точку в (\textbf{1}, \textbf{3}), а финиш в (\textbf{2}, \textbf{3}). Существует \textbf{4} пути от старта до контрольной точки. От контрольной точки до финиша можно добраться только по единственному пути, сделав при этом минимальное количество шагов. Таким образом всего существует \textbf{4} различных кратчайших пути, длина которых равна \textbf{T = 2 + 3 = 5}. Однако имеется лучший вариант выбора контрольной точки и финиша. Расположим контрольную точку в (\textbf{1}, \textbf{1}), а финиш в (\textbf{2}, \textbf{2}). Существует два пути от старта до контрольной точки. Аналогично имеется в точности два пути добраться от контрольной точки до финиша. Что в целом дает \textbf{4} различных кратчайших пути. Длина этих путей равна \textbf{T = 2 + 2 = 4}. Будучи гонщиком Хакер Капа, Вам следует решить где расположить контрольную точку и финиш чтобы не проиграть. По заданному \textbf{S} найдите наименьшее возможное \textbf{T}, которое достигается при всех возможных местоположениях контрольной точки и финиша, чтобы существовало в точности \textbf{S} различных кратчайших путей от старта до финиша, проходящих через контрольную точку. \InputFile Первая строка содержит количество гонок \textbf{R (R }≤\textbf{ 20)}, в которых Вы принимаете участие. Далее следуют \textbf{R} строк, каждая из которых описывает гонку одним значением \textbf{S} (\textbf{1} ≤ \textbf{S} ≤ \textbf{10000000}). Строки между собой разделяются символом "\textbf{\textbackslash n}". \OutputFile Для каждой гонки в отдельной строке вывести ее номер как показано в примере, а также наименьшую возможную длину кратчайшего пути \textbf{T}.