Джимми необходимо вычислить функцию $f(x, y)$, где $x$ и $y$ целые числа в промежутке от $1$ до $n$. Если ему известно $f(x, y)$, то он легко может найти $f(k \cdot x, k \cdot y)$, где $k$ --- любое целое число, выполнив простейшие вычисления над $f(x, y)$ и $k$. Отметим, что функция $f$ не симметрична, поэтому значение $f(x, y)$ не может быть получено из $f(y, x)$. Например, если $n = 4$, то Джимми изначально достаточно знать $11$ из $16$ возможных входных комбинаций: \includegraphics{https://static.e-olymp.com/content/0b/0b289e6798ccd6949ede3090b3e6b17efc8d825b.gif} Оставшиеся $5$ значений он может без труда вычислить из уже имеющихся: \begin{itemize} \item $f(2, 2), f(3, 3)$ и $f(4, 4)$ из $f(1, 1)$; \item $f(2, 4)$ из $f(1, 2)$; \item $f(4, 2)$ из $f(2, 1)$; \end{itemize} \InputFile Состоит из не более чем $600$ строк. Каждая строка содержит одно целое число $n~(1 \le n \le 50000)$. Последняя строка содержит ноль и не обрабатывается. \OutputFile Для каждого входного значения $n$ в отдельной строке вывести минимальное количество значений функций, которое следует знать Джимми для вычисления всех $n^2$ значений $f(x, y)$.