#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <chrono>
#include <cmath>
#include <complex>
#include <deque>
#include <forward_list>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iostream>
#include <limits>
#include <list>
#include <map>
#include <memory>
#include <numeric>
#include <optional>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

#ifdef RUTHEN_LOCAL
#include <debug.hpp>
#else
#define show(x) true
#endif

// type definition
using i64 = long long;
using u32 = unsigned int;
using u64 = unsigned long long;
using f32 = float;
using f64 = double;
using f128 = long double;
template <class T> using pque = std::priority_queue<T>;
template <class T> using pqueg = std::priority_queue<T, std::vector<T>, std::greater<T>>;
// overload
#define overload4(_1, _2, _3, _4, name, ...) name
#define overload3(_1, _2, _3, name, ...) name
#define overload2(_1, _2, name, ...) name
// for loop
#define REP1(a) for (long long _ = 0; _ < (a); _++)
#define REP2(i, a) for (long long i = 0; i < (a); i++)
#define REP3(i, a, b) for (long long i = (a); i < (b); i++)
#define REP4(i, a, b, c) for (long long i = (a); i < (b); i += (c))
#define REP(...) overload4(__VA_ARGS__, REP4, REP3, REP2, REP1)(__VA_ARGS__)
#define RREP1(a) for (long long _ = (a)-1; _ >= 0; _--)
#define RREP2(i, a) for (long long i = (a)-1; i >= 0; i--)
#define RREP3(i, a, b) for (long long i = (b)-1; i >= (a); i--)
#define RREP(...) overload3(__VA_ARGS__, RREP3, RREP2, RREP1)(__VA_ARGS__)
#define FORE1(x, a) for (auto &&x : a)
#define FORE2(x, y, a) for (auto &&[x, y] : a)
#define FORE3(x, y, z, a) for (auto &&[x, y, z] : a)
#define FORE(...) overload4(__VA_ARGS__, FORE3, FORE2, FORE1)(__VA_ARGS__)
#define FORSUB(t, s) for (long long t = (s); t >= 0; t = (t == 0 ? -1 : (t - 1) & (s)))
// function
#define ALL(a) (a).begin(), (a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define SORT(a) std::sort((a).begin(), (a).end())
#define RSORT(a) std::sort((a).rbegin(), (a).rend())
#define REV(a) std::reverse((a).begin(), (a).end())
#define UNIQUE(a)                      \
    std::sort((a).begin(), (a).end()); \
    (a).erase(std::unique((a).begin(), (a).end()), (a).end())
#define LEN(a) (int)((a).size())
#define MIN(a) *std::min_element((a).begin(), (a).end())
#define MAX(a) *std::max_element((a).begin(), (a).end())
#define SUM1(a) std::accumulate((a).begin(), (a).end(), 0LL)
#define SUM2(a, x) std::accumulate((a).begin(), (a).end(), (x))
#define SUM(...) overload2(__VA_ARGS__, SUM2, SUM1)(__VA_ARGS__)
#define LB(a, x) std::distance((a).begin(), std::lower_bound((a).begin(), (a).end(), (x)))
#define UB(a, x) std::distance((a).begin(), std::upper_bound((a).begin(), (a).end(), (x)))
template <class T, class U> inline bool chmin(T &a, const U &b) { return (a > T(b) ? a = b, 1 : 0); }
template <class T, class U> inline bool chmax(T &a, const U &b) { return (a < T(b) ? a = b, 1 : 0); }
template <class T, class S> inline T floor(const T x, const S y) {
    assert(y);
    return (y < 0 ? floor(-x, -y) : (x > 0 ? x / y : x / y - (x % y == 0 ? 0 : 1)));
}
template <class T, class S> inline T ceil(const T x, const S y) {
    assert(y);
    return (y < 0 ? ceil(-x, -y) : (x > 0 ? (x + y - 1) / y : x / y));
}
template <class T, class S> std::pair<T, T> inline divmod(const T x, const S y) {
    T q = floor(x, y);
    return {q, x - q * y};
}
// 10 ^ n
constexpr long long TEN(int n) { return (n == 0) ? 1 : 10LL * TEN(n - 1); }
// 1 + 2 + ... + n
#define TRI1(n) ((n) * ((n) + 1LL) / 2)
// l + (l + 1) + ... + r
#define TRI2(l, r) (((l) + (r)) * ((r) - (l) + 1LL) / 2)
#define TRI(...) overload2(__VA_ARGS__, TRI2, TRI1)(__VA_ARGS__)
// bit operation
// bit[i] (= 0 or 1)
#define IBIT(bit, i) (((bit) >> (i)) & 1)
// (0, 1, 2, 3, 4) -> (0, 1, 3, 7, 15)
#define MASK(n) ((1LL << (n)) - 1)
#define POW2(n) (1LL << (n))
// (0, 1, 2, 3, 4) -> (0, 1, 1, 2, 1)
int popcnt(int x) { return __builtin_popcount(x); }
int popcnt(u32 x) { return __builtin_popcount(x); }
int popcnt(i64 x) { return __builtin_popcountll(x); }
int popcnt(u64 x) { return __builtin_popcountll(x); }
// (0, 1, 2, 3, 4) -> (-1, 0, 1, 1, 2)
int topbit(int x) { return (x == 0 ? -1 : 31 - __builtin_clz(x)); }
int topbit(u32 x) { return (x == 0 ? -1 : 31 - __builtin_clz(x)); }
int topbit(i64 x) { return (x == 0 ? -1 : 63 - __builtin_clzll(x)); }
int topbit(u64 x) { return (x == 0 ? -1 : 63 - __builtin_clzll(x)); }
// (0, 1, 2, 3, 4) -> (-1, 0, 1, 0, 2)
int lowbit(int x) { return (x == 0 ? -1 : __builtin_ctz(x)); }
int lowbit(u32 x) { return (x == 0 ? -1 : __builtin_ctz(x)); }
int lowbit(i64 x) { return (x == 0 ? -1 : __builtin_ctzll(x)); }
int lowbit(u64 x) { return (x == 0 ? -1 : __builtin_ctzll(x)); }
// binary search
template <class T, class F> T bin_search(T ok, T ng, F &f) {
    while ((ok > ng ? ok - ng : ng - ok) > 1) {
        T md = (ng + ok) >> 1;
        (f(md) ? ok : ng) = md;
    }
    return ok;
}
template <class T, class F> T bin_search_real(T ok, T ng, F &f, const int iter = 100) {
    for (int _ = 0; _ < iter; _++) {
        T md = (ng + ok) / 2;
        (f(md) ? ok : ng) = md;
    }
    return ok;
}
// rotate matrix counterclockwise by pi / 2
template <class T> void rot(std::vector<std::vector<T>> &a) {
    if ((int)(a.size()) == 0) return;
    if ((int)(a[0].size()) == 0) return;
    int n = (int)(a.size()), m = (int)(a[0].size());
    std::vector res(m, std::vector<T>(n));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            res[m - 1 - j][i] = a[i][j];
        }
    }
    a.swap(res);
}
// const value
constexpr int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
constexpr int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};
// infinity
template <class T> constexpr T INF = 0;
template <> constexpr int INF<int> = 1'000'000'000;                 // 1e9
template <> constexpr i64 INF<i64> = i64(INF<int>) * INF<int> * 2;  // 2e18
template <> constexpr u32 INF<u32> = INF<int>;                      // 1e9
template <> constexpr u64 INF<u64> = INF<i64>;                      // 2e18
template <> constexpr f32 INF<f32> = INF<i64>;                      // 2e18
template <> constexpr f64 INF<f64> = INF<i64>;                      // 2e18
template <> constexpr f128 INF<f128> = INF<i64>;                    // 2e18
// I/O
// input
template <class T> std::istream &operator>>(std::istream &is, std::vector<T> &v) {
    for (auto &&i : v) is >> i;
    return is;
}
template <class... T> void in(T &...a) { (std::cin >> ... >> a); }
void scan() {}
template <class Head, class... Tail> void scan(Head &head, Tail &...tail) {
    in(head);
    scan(tail...);
}
// input macro
#define INT(...)     \
    int __VA_ARGS__; \
    scan(__VA_ARGS__)
#define I64(...)     \
    i64 __VA_ARGS__; \
    scan(__VA_ARGS__)
#define U32(...)     \
    u32 __VA_ARGS__; \
    scan(__VA_ARGS__)
#define U64(...)     \
    u64 __VA_ARGS__; \
    scan(__VA_ARGS__)
#define F32(...)     \
    f32 __VA_ARGS__; \
    scan(__VA_ARGS__)
#define F64(...)     \
    f64 __VA_ARGS__; \
    scan(__VA_ARGS__)
#define F128(...)     \
    f128 __VA_ARGS__; \
    scan(__VA_ARGS__)
#define STR(...)             \
    std::string __VA_ARGS__; \
    scan(__VA_ARGS__)
#define CHR(...)      \
    char __VA_ARGS__; \
    scan(__VA_ARGS__)
#define VEC(type, name, size)     \
    std::vector<type> name(size); \
    scan(name)
#define VEC2(type, name1, name2, size)          \
    std::vector<type> name1(size), name2(size); \
    for (int i = 0; i < size; i++) scan(name1[i], name2[i])
#define VEC3(type, name1, name2, name3, size)                \
    std::vector<type> name1(size), name2(size), name3(size); \
    for (int i = 0; i < size; i++) scan(name1[i], name2[i], name3[i])
#define VEC4(type, name1, name2, name3, name4, size)                      \
    std::vector<type> name1(size), name2(size), name3(size), name4(size); \
    for (int i = 0; i < size; i++) scan(name1[i], name2[i], name3[i], name4[i])
#define VV(type, name, h, w)                       \
    std::vector name((h), std::vector<type>((w))); \
    scan(name)
// output
template <class T> std::ostream &operator<<(std::ostream &os, const std::vector<T> &v) {
    auto n = v.size();
    for (size_t i = 0; i < n; i++) {
        if (i) os << ' ';
        os << v[i];
    }
    return os;
}
template <class... T> void out(const T &...a) { (std::cout << ... << a); }
void print() { out('\n'); }
template <class Head, class... Tail> void print(Head &&head, Tail &&...tail) {
    out(head);
    if (sizeof...(Tail)) out(' ');
    print(tail...);
}
// for interactive problems
void printi() { std::cout << std::endl; }
template <class Head, class... Tail> void printi(Head &&head, Tail &&...tail) {
    out(head);
    if (sizeof...(Tail)) out(' ');
    printi(tail...);
}
// bool output
void YES(bool t = 1) { print(t ? "YES" : "NO"); }
void Yes(bool t = 1) { print(t ? "Yes" : "No"); }
void yes(bool t = 1) { print(t ? "yes" : "no"); }
void NO(bool t = 1) { YES(!t); }
void No(bool t = 1) { Yes(!t); }
void no(bool t = 1) { yes(!t); }
void POSSIBLE(bool t = 1) { print(t ? "POSSIBLE" : "IMPOSSIBLE"); }
void Possible(bool t = 1) { print(t ? "Possible" : "Impossible"); }
void possible(bool t = 1) { print(t ? "possible" : "impossible"); }
void IMPOSSIBLE(bool t = 1) { POSSIBLE(!t); }
void Impossible(bool t = 1) { Possible(!t); }
void impossible(bool t = 1) { possible(!t); }
void FIRST(bool t = 1) { print(t ? "FIRST" : "SECOND"); }
void First(bool t = 1) { print(t ? "First" : "Second"); }
void first(bool t = 1) { print(t ? "first" : "second"); }
void SECOND(bool t = 1) { FIRST(!t); }
void Second(bool t = 1) { First(!t); }
void second(bool t = 1) { first(!t); }
// I/O speed up
struct SetUpIO {
    SetUpIO() {
        std::ios::sync_with_stdio(false);
        std::cin.tie(0);
        std::cout << std::fixed << std::setprecision(15);
    }
} set_up_io;
using namespace std;

// https://nyaannyaan.github.io/library/prime/fast-factorize.hpp

#include <cstdint>
using namespace std;

using namespace std;

namespace internal {
template <typename T> using is_broadly_integral = typename conditional_t<is_integral_v<T> || is_same_v<T, __int128_t> || is_same_v<T, __uint128_t>, true_type, false_type>::type;

template <typename T> using is_broadly_signed = typename conditional_t<is_signed_v<T> || is_same_v<T, __int128_t>, true_type, false_type>::type;

template <typename T> using is_broadly_unsigned = typename conditional_t<is_unsigned_v<T> || is_same_v<T, __uint128_t>, true_type, false_type>::type;

#define ENABLE_VALUE(x) template <typename T> constexpr bool x##_v = x<T>::value;

ENABLE_VALUE(is_broadly_integral);
ENABLE_VALUE(is_broadly_signed);
ENABLE_VALUE(is_broadly_unsigned);
#undef ENABLE_VALUE

#define ENABLE_HAS_TYPE(var)                                                        \
    template <class, class = void> struct has_##var : false_type {};                \
    template <class T> struct has_##var<T, void_t<typename T::var>> : true_type {}; \
    template <class T> constexpr auto has_##var##_v = has_##var<T>::value;

#define ENABLE_HAS_VAR(var)                                                          \
    template <class, class = void> struct has_##var : false_type {};                 \
    template <class T> struct has_##var<T, void_t<decltype(T::var)>> : true_type {}; \
    template <class T> constexpr auto has_##var##_v = has_##var<T>::value;

}  // namespace internal

namespace internal {

using namespace std;

// a mod p
template <typename T> T safe_mod(T a, T p) {
    a %= p;
    if constexpr (is_broadly_signed_v<T>) {
        if (a < 0) a += p;
    }
    return a;
}

// 返り値：pair(g, x)
// s.t. g = gcd(a, b), xa = g (mod b), 0 <= x < b/g
template <typename T> pair<T, T> inv_gcd(T a, T p) {
    static_assert(is_broadly_signed_v<T>);
    a = safe_mod(a, p);
    if (a == 0) return {p, 0};
    T b = p, x = 1, y = 0;
    while (a != 0) {
        T q = b / a;
        swap(a, b %= a);
        swap(x, y -= q * x);
    }
    if (y < 0) y += p / b;
    return {b, y};
}

// 返り値 : a^{-1} mod p
// gcd(a, p) != 1 が必要
template <typename T> T inv(T a, T p) {
    static_assert(is_broadly_signed_v<T>);
    a = safe_mod(a, p);
    T b = p, x = 1, y = 0;
    while (a != 0) {
        T q = b / a;
        swap(a, b %= a);
        swap(x, y -= q * x);
    }
    assert(b == 1);
    return y < 0 ? y + p : y;
}

// T : 底の型
// U : T*T がオーバーフローしない かつ 指数の型
template <typename T, typename U> T modpow(T a, U n, T p) {
    a = safe_mod(a, p);
    T ret = 1 % p;
    while (n != 0) {
        if (n % 2 == 1) ret = U(ret) * a % p;
        a = U(a) * a % p;
        n /= 2;
    }
    return ret;
}

// 返り値 : pair(rem, mod)
// 解なしのときは {0, 0} を返す
template <typename T> pair<T, T> crt(const vector<T> &r, const vector<T> &m) {
    static_assert(is_broadly_signed_v<T>);
    assert(r.size() == m.size());
    int n = int(r.size());
    T r0 = 0, m0 = 1;
    for (int i = 0; i < n; i++) {
        assert(1 <= m[i]);
        T r1 = safe_mod(r[i], m[i]), m1 = m[i];
        if (m0 < m1) swap(r0, r1), swap(m0, m1);
        if (m0 % m1 == 0) {
            if (r0 % m1 != r1) return {0, 0};
            continue;
        }
        auto [g, im] = inv_gcd(m0, m1);
        T u1 = m1 / g;
        if ((r1 - r0) % g) return {0, 0};
        T x = (r1 - r0) / g % u1 * im % u1;
        r0 += x * m0;
        m0 *= u1;
        if (r0 < 0) r0 += m0;
    }
    return {r0, m0};
}

}  // namespace internal

using namespace std;

namespace internal {
unsigned long long non_deterministic_seed() {
    unsigned long long m = chrono::duration_cast<chrono::nanoseconds>(chrono::high_resolution_clock::now().time_since_epoch()).count();
    m ^= 9845834732710364265uLL;
    m ^= m << 24, m ^= m >> 31, m ^= m << 35;
    return m;
}
unsigned long long deterministic_seed() { return 88172645463325252UL; }

// 64 bit の seed 値を生成 (手元では seed 固定)
// 連続で呼び出すと同じ値が何度も返ってくるので注意
// #define RANDOMIZED_SEED するとシードがランダムになる
unsigned long long seed() {
#if defined(NyaanLocal) && !defined(RANDOMIZED_SEED)
    return deterministic_seed();
#else
    return non_deterministic_seed();
#endif
}

}  // namespace internal

namespace my_rand {
using i64 = long long;
using u64 = unsigned long long;

// [0, 2^64 - 1)
u64 rng() {
    static u64 _x = internal::seed();
    return _x ^= _x << 7, _x ^= _x >> 9;
}

// [l, r]
i64 rng(i64 l, i64 r) {
    assert(l <= r);
    return l + rng() % u64(r - l + 1);
}

// [l, r)
i64 randint(i64 l, i64 r) {
    assert(l < r);
    return l + rng() % u64(r - l);
}

// choose n numbers from [l, r) without overlapping
vector<i64> randset(i64 l, i64 r, i64 n) {
    assert(l <= r && n <= r - l);
    unordered_set<i64> s;
    for (i64 i = n; i; --i) {
        i64 m = randint(l, r + 1 - i);
        if (s.find(m) != s.end()) m = r - i;
        s.insert(m);
    }
    vector<i64> ret;
    for (auto &x : s) ret.push_back(x);
    sort(begin(ret), end(ret));
    return ret;
}

// [0.0, 1.0)
double rnd() { return rng() * 5.42101086242752217004e-20; }
// [l, r)
double rnd(double l, double r) {
    assert(l < r);
    return l + rnd() * (r - l);
}

template <typename T> void randshf(vector<T> &v) {
    int n = v.size();
    for (int i = 1; i < n; i++) swap(v[i], v[randint(0, i + 1)]);
}

}  // namespace my_rand

using my_rand::randint;
using my_rand::randset;
using my_rand::randshf;
using my_rand::rnd;
using my_rand::rng;

using namespace std;

template <typename Int, typename UInt, typename Long, typename ULong, int id> struct ArbitraryLazyMontgomeryModIntBase {
    using mint = ArbitraryLazyMontgomeryModIntBase;

    inline static UInt mod;
    inline static UInt r;
    inline static UInt n2;
    static constexpr int bit_length = sizeof(UInt) * 8;

    static UInt get_r() {
        UInt ret = mod;
        while (mod * ret != 1) ret *= UInt(2) - mod * ret;
        return ret;
    }
    static void set_mod(UInt m) {
        assert(m < (UInt(1u) << (bit_length - 2)));
        assert((m & 1) == 1);
        mod = m, n2 = -ULong(m) % m, r = get_r();
    }
    UInt a;

    ArbitraryLazyMontgomeryModIntBase() : a(0) {}
    ArbitraryLazyMontgomeryModIntBase(const Long &b) : a(reduce(ULong(b % mod + mod) * n2)){};

    static UInt reduce(const ULong &b) { return (b + ULong(UInt(b) * UInt(-r)) * mod) >> bit_length; }

    mint &operator+=(const mint &b) {
        if (Int(a += b.a - 2 * mod) < 0) a += 2 * mod;
        return *this;
    }
    mint &operator-=(const mint &b) {
        if (Int(a -= b.a) < 0) a += 2 * mod;
        return *this;
    }
    mint &operator*=(const mint &b) {
        a = reduce(ULong(a) * b.a);
        return *this;
    }
    mint &operator/=(const mint &b) {
        *this *= b.inverse();
        return *this;
    }

    mint operator+(const mint &b) const { return mint(*this) += b; }
    mint operator-(const mint &b) const { return mint(*this) -= b; }
    mint operator*(const mint &b) const { return mint(*this) *= b; }
    mint operator/(const mint &b) const { return mint(*this) /= b; }

    bool operator==(const mint &b) const { return (a >= mod ? a - mod : a) == (b.a >= mod ? b.a - mod : b.a); }
    bool operator!=(const mint &b) const { return (a >= mod ? a - mod : a) != (b.a >= mod ? b.a - mod : b.a); }
    mint operator-() const { return mint(0) - mint(*this); }
    mint operator+() const { return mint(*this); }

    mint pow(ULong n) const {
        mint ret(1), mul(*this);
        while (n > 0) {
            if (n & 1) ret *= mul;
            mul *= mul, n >>= 1;
        }
        return ret;
    }

    friend ostream &operator<<(ostream &os, const mint &b) { return os << b.get(); }

    friend istream &operator>>(istream &is, mint &b) {
        Long t;
        is >> t;
        b = ArbitraryLazyMontgomeryModIntBase(t);
        return (is);
    }

    mint inverse() const {
        Int x = get(), y = get_mod(), u = 1, v = 0;
        while (y > 0) {
            Int t = x / y;
            swap(x -= t * y, y);
            swap(u -= t * v, v);
        }
        return mint{u};
    }

    UInt get() const {
        UInt ret = reduce(a);
        return ret >= mod ? ret - mod : ret;
    }

    static UInt get_mod() { return mod; }
};

// id に適当な乱数を割り当てて使う
template <int id> using ArbitraryLazyMontgomeryModInt = ArbitraryLazyMontgomeryModIntBase<int, unsigned int, long long, unsigned long long, id>;
template <int id> using ArbitraryLazyMontgomeryModInt64bit = ArbitraryLazyMontgomeryModIntBase<long long, unsigned long long, __int128_t, __uint128_t, id>;

using namespace std;

namespace fast_factorize {

template <typename T, typename U> bool miller_rabin(const T &n, vector<T> ws) {
    if (n <= 2) return n == 2;
    if (n % 2 == 0) return false;

    T d = n - 1;
    while (d % 2 == 0) d /= 2;
    U e = 1, rev = n - 1;
    for (T w : ws) {
        if (w % n == 0) continue;
        T t = d;
        U y = internal::modpow<T, U>(w, t, n);
        while (t != n - 1 && y != e && y != rev) y = y * y % n, t *= 2;
        if (y != rev && t % 2 == 0) return false;
    }
    return true;
}

bool miller_rabin_u64(unsigned long long n) { return miller_rabin<unsigned long long, __uint128_t>(n, {2, 325, 9375, 28178, 450775, 9780504, 1795265022}); }

template <typename mint> bool miller_rabin(unsigned long long n, vector<unsigned long long> ws) {
    if (n <= 2) return n == 2;
    if (n % 2 == 0) return false;

    if (mint::get_mod() != n) mint::set_mod(n);
    unsigned long long d = n - 1;
    while (~d & 1) d >>= 1;
    mint e = 1, rev = n - 1;
    for (unsigned long long w : ws) {
        if (w % n == 0) continue;
        unsigned long long t = d;
        mint y = mint(w).pow(t);
        while (t != n - 1 && y != e && y != rev) y *= y, t *= 2;
        if (y != rev && t % 2 == 0) return false;
    }
    return true;
}

bool is_prime(unsigned long long n) {
    using mint32 = ArbitraryLazyMontgomeryModInt<96229631>;
    using mint64 = ArbitraryLazyMontgomeryModInt64bit<622196072>;

    if (n <= 2) return n == 2;
    if (n % 2 == 0) return false;
    if (n < (1uLL << 30)) {
        return miller_rabin<mint32>(n, {2, 7, 61});
    } else if (n < (1uLL << 62)) {
        return miller_rabin<mint64>(n, {2, 325, 9375, 28178, 450775, 9780504, 1795265022});
    } else {
        return miller_rabin_u64(n);
    }
}

}  // namespace fast_factorize

using fast_factorize::is_prime;

/**
 * @brief Miller-Rabin primality test
 */

namespace fast_factorize {
using u64 = uint64_t;

template <typename mint, typename T> T pollard_rho(T n) {
    if (~n & 1) return 2;
    if (is_prime(n)) return n;
    if (mint::get_mod() != n) mint::set_mod(n);
    mint R, one = 1;
    auto f = [&](mint x) { return x * x + R; };
    auto rnd_ = [&]() { return rng() % (n - 2) + 2; };
    while (1) {
        mint x, y, ys, q = one;
        R = rnd_(), y = rnd_();
        T g = 1;
        constexpr int m = 128;
        for (int r = 1; g == 1; r <<= 1) {
            x = y;
            for (int i = 0; i < r; ++i) y = f(y);
            for (int k = 0; g == 1 && k < r; k += m) {
                ys = y;
                for (int i = 0; i < m && i < r - k; ++i) q *= x - (y = f(y));
                g = gcd(q.get(), n);
            }
        }
        if (g == n) do
                g = gcd((x - (ys = f(ys))).get(), n);
            while (g == 1);
        if (g != n) return g;
    }
    exit(1);
}

using i64 = long long;

vector<i64> inner_factorize(u64 n) {
    using mint32 = ArbitraryLazyMontgomeryModInt<452288976>;
    using mint64 = ArbitraryLazyMontgomeryModInt64bit<401243123>;

    if (n <= 1) return {};
    u64 p;
    if (n <= (1LL << 30)) {
        p = pollard_rho<mint32, uint32_t>(n);
    } else if (n <= (1LL << 62)) {
        p = pollard_rho<mint64, uint64_t>(n);
    } else {
        exit(1);
    }
    if (p == n) return {i64(p)};
    auto l = inner_factorize(p);
    auto r = inner_factorize(n / p);
    copy(begin(r), end(r), back_inserter(l));
    return l;
}

vector<i64> factorize(u64 n) {
    auto ret = inner_factorize(n);
    sort(begin(ret), end(ret));
    return ret;
}

map<i64, i64> factor_count(u64 n) {
    map<i64, i64> mp;
    for (auto &x : factorize(n)) mp[x]++;
    return mp;
}

vector<i64> divisors(u64 n) {
    if (n == 0) return {};
    vector<pair<i64, i64>> v;
    for (auto &p : factorize(n)) {
        if (v.empty() || v.back().first != p) {
            v.emplace_back(p, 1);
        } else {
            v.back().second++;
        }
    }
    vector<i64> ret;
    auto f = [&](auto rc, int i, i64 x) -> void {
        if (i == (int)v.size()) {
            ret.push_back(x);
            return;
        }
        rc(rc, i + 1, x);
        for (int j = 0; j < v[i].second; j++) rc(rc, i + 1, x *= v[i].first);
    };
    f(f, 0, 1);
    sort(begin(ret), end(ret));
    return ret;
}

}  // namespace fast_factorize

using fast_factorize::divisors;
using fast_factorize::factor_count;
using fast_factorize::factorize;

/**
 * @brief 高速素因数分解(Miller Rabin/Pollard's Rho)
 * @docs docs/prime/fast-factorize.md
 */

// constexpr ... for constexpr bool prime()
template <int m> struct StaticModint {
    using mint = StaticModint;
    unsigned int _v;

    static constexpr int mod() { return m; }
    static constexpr unsigned int umod() { return m; }

    constexpr StaticModint() : _v(0) {}

    template <class T> constexpr StaticModint(T v) {
        long long x = (long long)(v % (long long)(umod()));
        if (x < 0) x += umod();
        _v = (unsigned int)(x);
    }

    constexpr unsigned int val() const { return _v; }

    constexpr mint &operator++() {
        _v++;
        if (_v == umod()) _v = 0;
        return *this;
    }
    constexpr mint &operator--() {
        if (_v == 0) _v = umod();
        _v--;
        return *this;
    }
    constexpr mint operator++(int) {
        mint result = *this;
        ++*this;
        return result;
    }
    constexpr mint operator--(int) {
        mint result = *this;
        --*this;
        return result;
    }

    constexpr mint &operator+=(const mint &rhs) {
        _v += rhs._v;
        if (_v >= umod()) _v -= umod();
        return *this;
    }
    constexpr mint &operator-=(const mint &rhs) {
        _v -= rhs._v;
        if (_v >= umod()) _v += umod();
        return *this;
    }
    constexpr mint &operator*=(const mint &rhs) {
        unsigned long long z = _v;
        z *= rhs._v;
        _v = (unsigned int)(z % umod());
        return *this;
    }
    constexpr mint &operator/=(const mint &rhs) { return (*this *= rhs.inv()); }

    constexpr mint operator+() const { return *this; }
    constexpr mint operator-() const { return mint() - *this; }

    constexpr mint pow(long long n) const {
        assert(n >= 0);
        mint x = *this, r = 1;
        while (n) {
            if (n & 1) r *= x;
            x *= x;
            n >>= 1;
        }
        return r;
    }

    constexpr mint inv() const {
        if (prime) {
            assert(_v);
            return pow(umod() - 2);
        } else {
            auto eg = inv_gcd(_v, m);
            assert(eg.first == 1);
            return eg.second;
        }
    }

    friend constexpr mint operator+(const mint &lhs, const mint &rhs) { return mint(lhs) += rhs; }
    friend constexpr mint operator-(const mint &lhs, const mint &rhs) { return mint(lhs) -= rhs; }
    friend constexpr mint operator*(const mint &lhs, const mint &rhs) { return mint(lhs) *= rhs; }
    friend constexpr mint operator/(const mint &lhs, const mint &rhs) { return mint(lhs) /= rhs; }
    friend constexpr bool operator==(const mint &lhs, const mint &rhs) { return lhs._v == rhs._v; }
    friend constexpr bool operator!=(const mint &lhs, const mint &rhs) { return lhs._v != rhs._v; }
    friend std::ostream &operator<<(std::ostream &os, const mint &v) { return os << v.val(); }

    static constexpr bool prime = []() -> bool {
        if (m == 1) return false;
        if (m == 2 || m == 7 || m == 61) return true;
        if (m % 2 == 0) return false;
        unsigned int d = m - 1;
        while (d % 2 == 0) d /= 2;
        for (unsigned int a : {2, 7, 61}) {
            unsigned int t = d;
            mint y = mint(a).pow(t);
            while (t != m - 1 and y != 1 and y != m - 1) {
                y *= y;
                t <<= 1;
            }
            if (y != m - 1 and t % 2 == 0) {
                return false;
            }
        }
        return true;
    }();
    static constexpr std::pair<int, int> inv_gcd(int a, int b) {
        if (a == 0) return {b, 0};
        int s = b, t = a, m0 = 0, m1 = 1;
        while (t) {
            const int u = s / t;
            s -= t * u;
            m0 -= m1 * u;
            std::swap(s, t);
            std::swap(m0, m1);
        }
        if (m0 < 0) m0 += b / s;
        return {s, m0};
    }
};
using mint107 = StaticModint<1000000007>;
using mint998 = StaticModint<998244353>;
using mint = mint998;

void solve() {
    I64(N);
    auto pf = factor_count(N);
    const int M = 60;
    const int L = LEN(pf);
    vector calc(L, vector<i64>(M + 1));
    int ind = 0;
    FORE(p, c, pf) {
        // {総和, 末尾}
        vector dp(M + 1, vector<i64>(M + 1));
        REP(i, c + 1) dp[i][i] = 1;
        REP(i, M) {
            REP(b, M + 1) { calc[ind][i + 1] += dp[c][b]; }
            vector np(M + 1, vector<i64>(M + 1));
            REP(s, M + 1) REP(b, M + 1) {
                if (dp[s][b] == 0) continue;
                REP(nx, b + 1) {
                    if (nx + s <= c) np[s + nx][nx] += dp[s][b];
                }
            }
            swap(dp, np);
        }
        ind++;
    }
    i64 ans = 0;
    REP(len, 1, M + 1) {
        mint c = 1;
        REP(i, L) c *= calc[i][len];
        mint er = 1;
        REP(i, L) er *= calc[i][len - 1];
        mint cur = c - er;
        ans += cur.val();
    }
    print(ans);
    return;
}

int main() {
    solve();
    return 0;
}