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