Джимі слід обчислити функцію $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)$.