Джимми необходимо вычислить функцию f(x,y), где x и y целые числа в промежутке от 1 до n. Если ему известно f(x,y), то он легко может найти f(k⋅x,k⋅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≤n≤50000). Последняя строка содержит ноль и не обрабатывается.
Для каждого входного значения n в отдельной строке вывести минимальное количество значений функций, которое следует знать Джимми для вычисления всех n2 значений f(x,y).