Віддаленаземля
У Республіці Віддаленій щороку святкують день незалежності. Проте, оскільки це сталося дуже давно, ніхто не може точно згадати дату. Відомо лише, що сьогодні кількість днів, які минули з моменту їхньої незалежності (D), є ідеальним квадратом. Більше того, це найбільше можливе число, яке можна отримати як добуток різних чисел, менших або рівних n.
Оскільки в Республіці Віддаленій рік складається з 1000000007 днів, громадянам потрібно знати лише D за модулем 1000000007. Зверніть увагу, що їх цікавить найбільше D, а не найбільше D за модулем 1000000007.
Вхідні дані
Кожен тестовий випадок подається одним рядком, що містить ціле число n (1 ≤ n ≤ 10000000). Вхід завершується рядком, що містить 0.
Вихідні дані
Для кожного тестового випадку виведіть кількість днів, що минули з моменту, коли Республіка стала незалежною, за модулем 1000000007, по одному на рядок.