Jimmy have to calculate a function $f(x, y)$ where $x$ and $y$ are both integers in the range from $1$ to $n$. When he knows $f(x, y)$, he can easily derive $f(k \cdot x, k \cdot y)$, where $k$ is any integer from it by applying some simple calculations involving $f(x, y)$ and $k$. Note that the function $f$ is not symmetric, so $f(x, y)$ can not be derived from $f(y, x)$. For example if $n = 4$, he only needs to know the answers for $11$ out of the $16$ possible input value combinations: \includegraphics{https://static.e-olymp.com/content/0b/0b289e6798ccd6949ede3090b3e6b17efc8d825b.gif} The other $5$ can be derived from them: \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 Consists of at most $600$ lines. Each line contains an integer $n~(1 \le n \le 50000)$. The last line contains one zero and should not be processed. \OutputFile For each input value of $n$ print in a separate line the minimum number of function values Jimmy needs to know to compute all $n^2$ values $f(x, y)$.