#include <bits/stdc++.h>
using i32 = int;
using u32 = unsigned int;
using i64 = long long;
using u64 = unsigned long long;
using i128 = __int128_t;
using u128 = __uint128_t;
using f64 = double;
using f80 = long double;
using f128 = __float128;
constexpr i32 operator"" _i32(u64 v) { return v; }
constexpr u32 operator"" _u32(u64 v) { return v; }
constexpr i64 operator"" _i64(u64 v) { return v; }
constexpr u64 operator"" _u64(u64 v) { return v; }
constexpr f64 operator"" _f64(f80 v) { return v; }
constexpr f80 operator"" _f80(f80 v) { return v; }
using Istream = std::istream;
using Ostream = std::ostream;
using Str = std::string;
template<typename T> using Lt = std::less<T>;
template<typename T> using Gt = std::greater<T>;
template<int n> using BSet = std::bitset<n>;
template<typename T1, typename T2> using Pair = std::pair<T1, T2>;
template<typename... Ts> using Tup = std::tuple<Ts...>;
template<typename T, int N> using Arr = std::array<T, N>;
template<typename... Ts> using Deq = std::deque<Ts...>;
template<typename... Ts> using Set = std::set<Ts...>;
template<typename... Ts> using MSet = std::multiset<Ts...>;
template<typename... Ts> using USet = std::unordered_set<Ts...>;
template<typename... Ts> using UMSet = std::unordered_multiset<Ts...>;
template<typename... Ts> using Map = std::map<Ts...>;
template<typename... Ts> using MMap = std::multimap<Ts...>;
template<typename... Ts> using UMap = std::unordered_map<Ts...>;
template<typename... Ts> using UMMap = std::unordered_multimap<Ts...>;
template<typename... Ts> using Vec = std::vector<Ts...>;
template<typename... Ts> using Stack = std::stack<Ts...>;
template<typename... Ts> using Queue = std::queue<Ts...>;
template<typename T> using MaxHeap = std::priority_queue<T>;
template<typename T> using MinHeap = std::priority_queue<T, Vec<T>, Gt<T>>;
template<typename T> using Opt = std::optional<T>;
constexpr bool LOCAL = false;
template<typename T> static constexpr T OjLocal(T oj, T local) { return LOCAL ? local : oj; }
template<typename T> constexpr T LIMMIN = std::numeric_limits<T>::min();
template<typename T> constexpr T LIMMAX = std::numeric_limits<T>::max();
template<typename T> constexpr T INF = (LIMMAX<T> - 1) / 2;
template<typename T = i64> constexpr T TEN(int N) { return N == 0 ? T{1} : TEN<T>(N - 1) * T{10}; }
constexpr auto ABS(auto x) { return (x >= 0 ? x : -x); }
auto makePair(const auto& x1, const auto& x2) { return std::make_pair(x1, x2); }
auto makeTup(const auto&... xs) { return std::make_tuple(xs...); }
template<typename T> constexpr bool chmin(T& x, const T& y, auto comp = Lt<T>{}) { return (comp(y, x) ? (x = y, true) : false); }
template<typename T> constexpr bool chmax(T& x, const T& y, auto comp = Lt<T>{}) { return (comp(x, y) ? (x = y, true) : false); }
constexpr i64 floorDiv(i64 x, i64 y)
{
    assert(y != 0);
    if (y < 0) { x = -x, y = -y; }
    return x >= 0 ? x / y : (x - y + 1) / y;
}
constexpr i64 ceilDiv(i64 x, i64 y)
{
    assert(y != 0);
    if (y < 0) { x = -x, y = -y; }
    return x >= 0 ? (x + y - 1) / y : x / y;
}
template<typename T> constexpr T powerSemiGroup(const T& x, i64 N, auto mul)
{
    assert(N > 0);
    if (N == 1) { return x; }
    return (N % 2 == 1 ? mul(x, powerSemiGroup(x, N - 1, mul)) : powerSemiGroup(mul(x, x), N / 2, mul));
}
template<typename T> constexpr auto powerSemiGroup(const auto& v, i64 N) { return powerSemiGroup(v, N, std::multiplies<T>{}); }
template<typename T> constexpr T powerMonoid(const T& x, i64 N, const T& e, auto mul)
{
    assert(N >= 0);
    return (N == 0 ? e : powerSemiGroup(x, N, mul));
}
template<typename T> constexpr T powerMonoid(T x, i64 N, const T& e) { return powerMonoid(x, N, e, std::multiplies<T>{}); }
template<typename T> constexpr T powerInt(T x, i64 N) { return powerMonoid(x, N, T{1}); }
constexpr u64 powerMod(u64 x, i64 N, u64 mod)
{
    assert(0 < mod);
    return powerMonoid(x, N, u64{1}, [&](u64 x, u64 y) {
        if (mod <= (u64)LIMMAX<u32>) {
            return x * y % mod;
        } else {
            return (u64)((u128)x * y % mod);
        }
    });
}
constexpr auto sumAll(const auto& xs) { return std::accumulate(std::begin(xs), std::end(xs), decltype(xs[0]){}); }
constexpr int lbInd(const auto& xs, const auto& x) { return std::ranges::lower_bound(xs, x) - std::begin(xs); }
constexpr int ubInd(const auto& xs, const auto& x) { return std::ranges::upper_bound(xs, x) - std::begin(xs); }
constexpr int find(const auto& xs, const auto& x)
{
    const int i = lbInd(xs, x);
    if (i < std::ssize(xs) and xs[i] == x) { return i; }
    return std::ssize(xs);
}
constexpr void concat(auto& xs1, const auto& xs2) { std::ranges::copy(xs2, std::back_inserter(xs1)); }
constexpr auto concatCopy(const auto& xs1, const auto& xs2)
{
    auto Ans = xs1;
    return concat(Ans, xs2), Ans;
}
template<typename Ts, typename T> constexpr void fillAll(Ts& arr, const T& x)
{
    if constexpr (std::is_convertible<T, Ts>::value) {
        arr = x;
    } else {
        for (auto& subarr : arr) { fillAll(subarr, x); }
    }
}
template<typename T> constexpr Vec<T> genVec(int N, auto gen)
{
    Vec<T> ans;
    std::ranges::generate_n(std::back_inserter(ans), N, gen);
    return ans;
}
constexpr auto minAll(const auto& xs, auto... args) { return std::ranges::min(xs, args...); }
constexpr auto maxAll(const auto& xs, auto... args) { return std::ranges::max(xs, args...); }
constexpr int minInd(const auto& xs, auto... args) { return std::ranges::min_element(xs, args...) - std::begin(xs); }
constexpr int maxInd(const auto& xs, auto... args) { return std::ranges::max_element(xs, args...) - std::begin(xs); }
template<typename T = int> constexpr Vec<T> iotaVec(int N, T offset = 0)
{
    Vec<T> ans(N);
    std::iota(std::begin(ans), std::end(ans), offset);
    return ans;
}
constexpr void plusAll(auto& xs, const auto& x)
{
    std::ranges::for_each(xs, [&](auto& e) { e += x; });
}
constexpr void reverseAll(auto& xs) { std::ranges::reverse(xs); }
constexpr void sortAll(auto& xs, auto... args) { std::ranges::sort(xs, args...); }
constexpr auto runLengthEncode(const auto& xs)
{
    using T = typename std::decay<decltype(xs[0])>::type;
    Vec<Pair<T, int>> Ans;
    auto [l, px] = makePair(0, T{});
    for (const T& x : xs) {
        if (l == 0 or x != px) {
            if (l > 0) { Ans.push_back({px, l}); }
            l = 1, px = x;
        } else {
            l++;
        }
    }
    if (l > 0) { Ans.push_back({px, l}); }
    return Ans;
}
inline Ostream& operator<<(Ostream& os, u128 v)
{
    Str ans;
    if (v == 0) { ans = "0"; }
    while (v) { ans.push_back('0' + v % 10), v /= 10; }
    std::reverse(ans.begin(), ans.end());
    return os << ans;
}
inline Ostream& operator<<(Ostream& os, i128 v)
{
    bool minus = false;
    if (v < 0) { minus = true, v = -v; }
    return os << (minus ? "-" : "") << (u128)v;
}
constexpr bool isBitOn(u64 x, int i) { return assert(0 <= i and i < 64), ((x >> i) & 1_u64); }
constexpr bool isBitOff(u64 x, int i) { return assert(0 <= i and i < 64), (not isBitOn(x, i)); }
constexpr u64 bitMask(int w) { return assert(0 <= w and w <= 64), (w == 64 ? ~0_u64 : (1_u64 << w) - 1); }
constexpr u64 bitMask(int s, int e) { return assert(0 <= s and s <= e and e <= 64), (bitMask(e - s) << s); }
constexpr int floorLog2(u64 x) { return 63 - std::countl_zero(x); }
constexpr int ceilLog2(u64 x) { return x == 0 ? -1 : std::bit_width(x - 1); }
constexpr int order2(u64 x) { return std::countr_zero(x); }
template<typename F> struct Fix : F
{
    constexpr Fix(F&& f) : F{std::forward<F>(f)} {}
    template<typename... Args> constexpr auto operator()(Args&&... args) const
    {
        return F::operator()(*this, std::forward<Args>(args)...);
    }
};
class irange
{
private:
    struct itr
    {
        constexpr itr(i64 start, i64 end, i64 step) : m_cnt{start}, m_step{step}, m_end{end}, m_inc{start <= end} {}
        constexpr bool operator!=(const itr&) const { return (m_inc ? m_cnt < m_end : m_end < m_cnt); }
        constexpr i64 operator*() { return m_cnt; }
        constexpr itr& operator++() { return m_cnt += m_step, *this; }
        i64 m_cnt, m_step, m_end;
        bool m_inc;
    };
    i64 m_start, m_end, m_step;
public:
    constexpr irange(i64 start, i64 end, i64 step = 1) : m_start{start}, m_end{end}, m_step{step} { assert(step != 0); }
    constexpr itr begin() const { return itr{m_start, m_end, m_step}; }
    constexpr itr end() const { return itr{m_start, m_end, m_step}; }
};
constexpr irange rep(i64 end) { return irange(0, end, 1); }
constexpr irange per(i64 rend) { return irange(rend - 1, -1, -1); }
constexpr Pair<i64, i64> extgcd(i64 a, i64 b)
{
    assert(a != 0 or b != 0);
    const i64 A = ABS(a), B = ABS(b);
    auto [x, y, g] = Fix([&](auto self, i64 a, i64 b) -> Tup<i64, i64, i64> {
        assert(0 <= a and a < b);
        if (a == 0) { return {0, 1, b}; }
        const auto [px, py, pg] = self(b % a, a);
        return {py - (b / a) * px, px, pg};
    })(std::ranges::min(A, B), std::ranges::max(A, B));
    if (A > B) { std::swap(x, y); }
    if (a < 0) { x = -x; }
    if (b < 0) { y = -y; }
    if (x < 0) { x += B / g, y -= (b > 0 ? a / g : -a / g); }
    return {x, y};
}
constexpr i64 inverseMod(i64 a, i64 mod)
{
    assert(mod > 0 and a % mod != 0);
    return extgcd(a % mod, mod).first;
}
constexpr i64 binSearch(i64 ng, i64 ok, auto check)
{
    while (ABS(ok - ng) > 1) {
        const i64 mid = (ok + ng) / 2;
        (check(mid) ? ok : ng) = mid;
    }
    return ok;
}
constexpr f80 binSearch(f80 ng, f80 ok, auto check, int times)
{
    for (auto _temp_name_0 [[maybe_unused]] : rep(times)) {
        const f80 mid = (ok + ng) / 2;
        (check(mid) ? ok : ng) = mid;
    }
    return ok;
}
constexpr u64 intNthRoot(u64 A, int K)
{
    assert(K > 0);
    if (A == 0) { return 0; }
    if (K == 1) { return A; }
    if (K > 64) { return 1; }
    return binSearch(1_i64 << 32, 1_i64, [&](i64 a) {
        u64 x = (u64)1;
        for (auto _temp_name_1 [[maybe_unused]] : rep(K)) {
            if (x > A / a) { return false; }
            x *= a;
        }
        return true;
    });
}
constexpr u64 intSqrt(u64 A) { return intNthRoot(A, 2); }
template<typename Engine> class RNG
{
public:
    using result_type = typename Engine::result_type;
    using U = result_type;
    static constexpr U min() { return Engine::min(); }
    static constexpr U max() { return Engine::max(); }
    RNG() : RNG(std::random_device{}()) {}
    RNG(U seed) : m_rng(seed) {}
    U operator()() { return m_rng(); }
    template<typename T>
        requires std::is_integral_v<T>
    T val(T min, T max)
    {
        return std::uniform_int_distribution<T>(min, max)(m_rng);
    }
    template<typename T> Vec<T> vec(int N, T min, T max)
    {
        return genVec<T>(N, [&]() { return val<T>(min, max); });
    }
private:
    Engine m_rng;
};
inline RNG<std::mt19937> rng;
inline RNG<std::mt19937_64> rng64;
constexpr u64 primitiveRoot(u64 P)
{
    assert(P >= 2);
    Vec<u64> ps;
    {
        u64 Q = P - 1;
        for (u64 p = 2; p * p <= P - 1; p++) {
            if (Q % p == 0) { ps.push_back(p); }
            while (Q % p == 0) { Q /= p; }
        }
        if (Q > 1) { ps.push_back(Q); }
    }
    for (u64 r = 1; r < P; r++) {
        bool ok = true;
        for (u64 p : ps) {
            const u64 Q = powerMod(r, (P - 1) / p, P);
            if (Q == 1) {
                ok = false;
                break;
            }
        }
        if (ok) { return r; }
    }
    return 0;
}
template<u64 Mod, bool dynamic = false>
    requires(dynamic or (0 < Mod and Mod <= (u64)LIMMAX<i64>))
class modint
{
public:
    static constexpr bool isDynamic() { return dynamic; }
    static constexpr u64 mod()
    {
        if constexpr (dynamic) {
            return modRef();
        } else {
            return Mod;
        }
    }
    static constexpr void setMod(u64 m)
        requires dynamic
    {
        assert(0 < m and m <= LIMMAX<i64>), modRef() = m;
    }
    constexpr modint() : m_val{0} {}
    constexpr modint(i64 v) : m_val{normll(v)} {}
    constexpr friend modint operator-(const modint& m) { return modint{0} - m; }
    constexpr friend modint& operator+=(modint& m1, const modint& m2) { return m1.m_val = norm(m1.m_val + m2.m_val), m1; }
    constexpr friend modint& operator-=(modint& m1, const modint& m2) { return m1.m_val = norm(m1.m_val + mod() - m2.m_val), m1; }
    constexpr friend modint& operator*=(modint& m1, const modint& m2)
    {
        if constexpr (dynamic) {
            if (mod() <= (u64)LIMMAX<u32>) {
                return (m1.m_val *= m2.m_val) %= mod(), m1;
            } else {
                return m1.m_val = (u64)((u128)m1.m_val * (u128)m2.m_val % (u128)mod()), m1;
            }
        } else {
            if constexpr (Mod <= (u64)LIMMAX<u32>) {
                return (m1.m_val *= m2.m_val) %= mod(), m1;
            } else {
                return m1.m_val = (u64)((u128)m1.m_val * (u128)m2.m_val % (u128)mod()), m1;
            }
        }
    }
    constexpr friend modint& operator/=(modint& m1, const modint& m2) { return m1 *= m2.inv(); }
    constexpr friend modint operator+(const modint& m1, const modint& m2)
    {
        auto ans = m1;
        return ans += m2;
    }
    constexpr friend modint operator-(const modint& m1, const modint& m2)
    {
        auto ans = m1;
        return ans -= m2;
    }
    constexpr friend modint operator*(const modint& m1, const modint& m2)
    {
        auto ans = m1;
        return ans *= m2;
    }
    constexpr friend modint operator/(const modint& m1, const modint& m2)
    {
        auto ans = m1;
        return ans /= m2;
    }
    constexpr friend bool operator==(const modint& m1, const modint& m2) { return m1.m_val == m2.m_val; }
    friend Istream& operator>>(Istream& is, modint& m)
    {
        i64 v;
        return is >> v, m = v, is;
    }
    friend Ostream& operator<<(Ostream& os, const modint& m) { return os << m.m_val; }
    constexpr u64 val() const { return m_val; }
    constexpr modint pow(i64 n) const { return powerInt(*this, n); }
    constexpr modint inv() const { return inverseMod(m_val, mod()); }
private:
    static u64& modRef()
        requires dynamic
    {
        static u64 mod_ = 0;
        return mod_;
    }
    static constexpr u64 norm(u64 x) { return x < mod() ? x : x - mod(); }
    static constexpr u64 normll(i64 x)
    {
        x %= mod();
        return norm(u64(x < 0 ? x + (i64)mod() : x));
    }
    u64 m_val;
};
using modint_1000000007 = modint<1000000007, false>;
using modint_998244353 = modint<998244353, false>;
template<u64 id>
    requires(id < (u64)LIMMAX<i64>)
using modint_dynamic = modint<id, true>;
template<u64 id>
    requires(id < (u64)LIMMAX<i64>)
using modint_dynamic_reserved = modint<id | (1_u64 << 63), true>;
constexpr bool millerRabin(u64 X, const Vec<u64>& as)
{
    using mint = modint_dynamic_reserved<81165>;
    mint::setMod(X);
    const u64 d = (X - 1) >> order2(X - 1);
    for (u64 a : as) {
        if (X <= a) { break; }
        u64 s = d;
        mint x = mint(a).pow(s);
        while (x != 1 and x != X - 1 and s != X - 1) { s *= 2, x *= x; }
        if (x != X - 1 and s % 2 == 0) { return false; }
    }
    return true;
}
constexpr bool isPrime(u64 X)
{
    if (X == 1) { return false; }
    if (X % 2 == 0) { return X == 2; }
    if (X < 4759123141_u64) {
        return millerRabin(X, {2_u64, 7_u64, 61_u64});
    } else {
        return millerRabin(X, {2_u64, 325_u64, 9375_u64, 28178_u64, 450775_u64, 9780504_u64, 1795265022_u64});
    }
}
constexpr u64 pollardRho(u64 X)
{
    assert(1 <= X and X <= (u64)LIMMAX<i64>);
    if (X % 2 == 0) { return 2; }
    if (X == 1 or isPrime(X)) { return X; }
    using mint = modint_dynamic_reserved<77726>;
    mint::setMod(X);
    auto f = [&](mint x, mint c) { return x * x + c; };
    const u64 gcdBlock = intNthRoot(X, 8);
    while (true) {
        const u64 a = rng64.val<u64>(0, X - 1);
        const mint c = rng64.val(2_u64, X - 1);
        mint x = a, y = a, sx = x, sy = y;
        mint p = 1;
        u64 g = 1;
        while (g == 1) {
            sx = x, sy = y;
            for (auto _temp_name_2 [[maybe_unused]] : rep(gcdBlock)) { x = f(x, c), y = f(f(y, c), c), p *= (x - y); }
            g = std::gcd(X, p.val());
        }
        if (g == X) {
            x = sx, y = sy, g = 1;
            while (g == 1) { x = f(x, c), y = f(f(y, c), c), g = std::gcd(X, (x - y).val()); }
        }
        if (g != X) { return g; }
    }
    return X;
}
constexpr Vec<Pair<u64, int>> primeFactors(u64 X)
{
    Vec<u64> Ans;
    Fix([&](auto dfs, u64 x) -> void {
        while (x % 2 == 0) { x /= 2, Ans.push_back(2); }
        if (x == 1) { return; }
        const u64 d = pollardRho(x);
        if (d == x) { return Ans.push_back(d), void(); }
        dfs(d), dfs(x / d);
    })(X);
    sortAll(Ans);
    return runLengthEncode(Ans);
}
constexpr Vec<u64> divisors(const Vec<Pair<u64, int>>& factors)
{
    Vec<u64> Ans{1};
    for (const auto& [p, e] : factors) {
        const int dn = (int)Ans.size();
        u64 pe = p;
        for (auto _temp_name_3 [[maybe_unused]] : rep(e)) {
            for (int j : rep(dn)) { Ans.push_back(Ans[j] * pe); }
            pe *= p;
        }
    }
    return sortAll(Ans), Ans;
}
template<typename mint> Opt<mint> modNthRoot(mint A, i64 K)
{
    constexpr auto Null = std::nullopt;
    const i64 P = mint::mod();
    if (K == 0) { return A == 1 ? Opt<mint>{1_i64} : Opt<mint>{Null}; }
    if (A == 0 or A == 1) { return A; }
    const i64 g = std::gcd(P - 1, K);
    if (A.pow((P - 1) / g) != 1) { return Null; }
    A = A.pow(inverseMod(K / g, (P - 1) / g));
    if (g == 1) { return A; }
    i64 Q = P - 1;
    Vec<Tup<i64, int, int>> factors;
    for (const auto& [p, a] : primeFactors(g)) {
        int b = 0;
        while (Q % p == 0) { Q /= p, b++; }
        factors.push_back({p, a, b});
    }
    mint X = 1;
    if (Q > 1) { X = A.pow(inverseMod(g, Q)); }
    for (const auto& [p, a, b] : factors) {
        if (a == b) { continue; }
        const i64 pa = powerInt(p, a), pb = powerInt(p, b);
        const i64 g0i = inverseMod(g / pa, pb / pa);
        auto ordLog_p = [&](mint X) {
            X = X.pow((P - 1) / pb);
            for (int i : per(b + 1)) {
                if (X == 1) { return i; }
                X = X.pow(p);
            }
            return 0;
        };
        auto trunc = [&](mint X, int ord) {
            assert(ord < b);
            for (auto _temp_name_4 [[maybe_unused]] : rep((b - 1) - ord)) { X = X.pow(p); }
            return X;
        };
        mint Eraser = 1;
        for (mint Z = 2;; Z += 1) {
            Eraser = Z.pow(Q);
            if (ordLog_p(Eraser) == 0) { break; }
        }
        Vec<mint> pErasers(b, Eraser);
        for (int i : rep(b - 1)) { pErasers[i + 1] = pErasers[i].pow(p); }
        const mint ipEraser = pErasers[b - 1].inv();
        const i64 M = std::max(1_i64, (i64)intSqrt(p * (b - a)));
        const i64 W = std::max(1_i64, (p - 1) / M);
        Map<u64, i64> Memo;
        for (mint E = 1, ER = pErasers[b - 1].pow(W); i64 x : rep(M + 1)) { Memo[E.val()] = W * x, E *= ER; }
        auto logErase = [&](mint X) {
            for (i64 i : rep(W)) {
                if (Memo.count(X.val()) > 0) { return Memo[X.val()] + i; }
                X *= ipEraser;
            }
            return -1_i64;
        };
        mint Error = X.pow(pa) / A.pow(g0i);
        while (true) {
            const int o = ordLog_p(Error);
            assert(o >= a);
            if (o == b) { break; }
            const i64 e = logErase(trunc(Error, o));
            X *= pErasers[o - a].pow(p - e), Error *= pErasers[o].pow(p - e);
        }
        Q *= pb;
    }
    return X;
}
class Printer
{
public:
    Printer(Ostream& os = std::cout) : m_os{os} { m_os << std::fixed << std::setprecision(15); }
    int operator()(const auto&... args) { return dump(args...), 0; }
    int ln(const auto&... args) { return dump(args...), m_os << '\n', 0; }
    int el(const auto&... args) { return dump(args...), m_os << std::endl, 0; }
private:
    void dump(const auto& v) { m_os << v; }
    int dump(const auto& v, const auto&... args) { return dump(v), m_os << ' ', dump(args...), 0; }
    template<typename... Args> void dump(const Vec<Args...>& vs)
    {
        for (Str delim = ""; const auto& v : vs) { m_os << std::exchange(delim, " "), dump(v); }
    }
    Ostream& m_os;
};
inline Printer out;
class Scanner
{
public:
    Scanner(Istream& is = std::cin) : m_is{is} { m_is.tie(nullptr)->sync_with_stdio(false); }
    template<typename T> T val()
    {
        T v;
        return m_is >> v, v;
    }
    template<typename T> T val(T offset) { return val<T>() - offset; }
    template<typename T> Vec<T> vec(int N)
    {
        return genVec<T>(N, [&]() { return val<T>(); });
    }
    template<typename T> Vec<T> vec(int N, T offset)
    {
        return genVec<T>(N, [&]() { return val<T>(offset); });
    }
    template<typename T> Vec<Vec<T>> vvec(int n, int m)
    {
        return genVec<Vec<T>>(n, [&]() { return vec<T>(m); });
    }
    template<typename T> Vec<Vec<T>> vvec(int n, int m, const T offset)
    {
        return genVec<Vec<T>>(n, [&]() { return vec<T>(m, offset); });
    }
    template<typename... Args> auto tup() { return Tup<Args...>{val<Args>()...}; }
    template<typename... Args> auto tup(Args... offsets) { return Tup<Args...>{val<Args>(offsets)...}; }
private:
    Istream& m_is;
};
inline Scanner in;
int main()
{
    const int T = in.val<int>();
    using mint = modint_dynamic<0>;
    for (auto _temp_name_5 [[maybe_unused]] : rep(T)) {
        const auto [P, K, Y] = in.tup<u64, i64, i64>();
        mint::setMod(P);
        const auto ans = modNthRoot(mint(Y), K);
        if (ans) {
            out.ln(ans.value());
        } else {
            out.ln(-1);
        }
    }
    return 0;
}