Хибний RSA#4665
Роман, Сергій та Андрій вирішили вдосконалити відомий алгоритм шифрування RSA. Вони вважають, що вимога, щоб модуль , який використовується в RSA, був добутком двох різних простих чисел, є зайвою. Замість цього вони планують використовувати , яке є добутком -тих степенів двох різних простих чисел: n = p^k q^k.
Однак, Нік зауважив, що, окрім усіх інших математичних проблем, цю схему може бути легше зламати. Тобто, важко факторизувати , яке є добутком двох різних простих чисел, тому що воно має рівно одну нетривіальну факторизацію. З іншого боку, у випадку n = p^k q^k може бути більше різних нетривіальних факторизацій. Наприклад, 100 = 2^2 \cdot 5^2 має вісім нетривіальних факторизацій: 100 = 2 \cdot 50, 100 = 2 \cdot 2 \cdot 25, 100 = 2 \cdot 2 \cdot 5 \cdot 5, 100 = 2 \cdot 5 \cdot 10, 100 = 4 \cdot 25, 100 = 4 \cdot 5 \cdot 5, 100 = 5 \cdot 20 та 100 = 10 \cdot 10.
Тепер Роман, Сергій та Андрій цікавляться — скільки різних нетривіальних факторизацій має n = p^k q^k?
Вхідний файл містить одне ціле число (6 \le n \le 10^{18}, гарантовано, що n = p^k q^k для різних простих чисел та і цілого числа k > 0).
Виведіть одне ціле число — кількість різних нетривіальних факторизацій .
Приклад 1