В магазине продаются плитки размером 1×1 упаковками по X штук. Какое минимальное количество упаковок надо купить, чтобы замостить плитками некоторый квадрат с целочисленными сторонами? Все плитки из купленных упаковок должны быть использованы.
Формат входных данных
В единственной строке вводится целое число X (1≤X≤1012).
Обратите внимание, что ответ может превышать возможное значение 32‑битной целочисленной переменной, поэтому необходимо использовать 64‑битные целочисленные типы данных (тип int6464 в языке Pascal, тип long long в C++, тип long в Java и C#).
Формат выходных данных
Выведите минимальное количество упаковок, которое надо купить. Можно доказать, что такое число всегда существует.
Система оценки
Решения, правильно работающие при X≤1000, будут оцениваться в 40 баллов.
Замечание
В примере в каждой упаковке по 12 плиток. Если мы купим одну упаковку, то не сможем замостить квадрат. Если купим 2 упаковки, то получится 24 плитки, которыми тоже нельзя замостить ни один квадрат. Если же купить 3 упаковки, то получится 36 плиток, ими можно замостить квадрат размера 6×6.