e-olymp

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

Джимми необходимо вычислить функцию Answer(x, y), где x и y целые числа в промежутке от 1 до n. Если ему известно Answer(x, y), то он легко может найти Answer(k * x, k * y), где k - любое целое, выполнив простейшие вычисления над Answer(x, y) и k.

Например, если n = 4, то Джимми изначально достаточно знать 11 из 16 возможных входных комбинаций: Answer(1, 1), Answer(1, 2), Answer(2, 1), Answer(1, 3), Answer(2, 3), Answer(3, 2), Answer(3, 1), Answer(1, 4), Answer(3, 4), Answer(4, 3) и Answer(4, 1). Оставшиеся 5 значений он может без труда вычислить из уже имеющихся (Answer(2, 2), Answer(3, 3) и Answer(4, 4) из Answer(1, 1), Answer(2, 4) из Answer(1, 2) и Answer(4, 2) из Answer(2, 1)). Отметим, что функция Answer не симметрична, поэтому Answer(3, 2) не может быть выведено из Answer(2, 3).

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

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

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

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

Лимит времени 1 секунда
Лимит использования памяти 128 MiB
Входные данные #1
2
5
0
Выходные данные #1
3
19