Послать таблицу

Джимми необходимо вычислить функцию $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$ возможных входных комбинаций:

Оставшиеся $5$ значений он может без труда вычислить из уже имеющихся:

• $f(2,2),f(3,3)$ и $f(4,4)$ из $f(1,1)$;

• $f(2,4)$ из $f(1,2)$;

• $f(4,2)$ из $f(2,1)$;

Входные данные

Состоит из не более чем $600$ строк. Каждая строка содержит одно целое число $n(1\le n\le 50000)$. Последняя строка содержит ноль и не обрабатывается.

Выходные данные

Для каждого входного значения $n$ в отдельной строке вывести минимальное количество значений функций, которое следует знать Джимми для вычисления всех $n^2$ значений $f(x,y)$.

Примеры