Надіслати таблицю#1563
Джиммі потрібно обчислити функцію f(x, y), де та — цілі числа від до . Якщо він знає f(x, y), то може легко отримати f(k \cdot x, k \cdot y) для будь-якого цілого , виконуючи прості обчислення на основі f(x, y) та .
Зверніть увагу, що функція не є симетричною, тому f(x, y) не можна отримати з f(y, x).
Наприклад, якщо n = 4, то спочатку Джиммі потрібно знати із можливих пар входів:
Решта значень можуть бути отримані з уже відомих:
f(2, 2), f(3, 3) та f(4, 4) — з f(1, 1);
f(2, 4) — з f(1, 2);
f(4, 2) — з f(2, 1);
Вхід містить не більше рядків. Кожен рядок містить одне ціле число (1 \le n \le 50000). Останній рядок містить і не підлягає обробці.
Для кожного вхідного значення виведіть в окремому рядку мінімальну кількість значень функції, які Джиммі потрібно знати, щоб обчислити всі n^2 значень f(x, y).
Приклад 1