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