#pragma GCC optimize("O3")
#pragma GCC optimize("fast-math")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx")
#pragma GCC target("avx2")
#include <bits/stdc++.h>
using namespace std;
using i8 = std::int8_t;
using u8 = std::uint8_t;
using i16 = std::int16_t;
using u16 = std::uint16_t;
using i32 = std::int32_t;
using u32 = std::uint32_t;
using i64 = std::int64_t;
using u64 = std::uint64_t;
using i128 = __int128_t;
using u128 = __uint128_t;
using ll = long long;
using ull = unsigned long long;
using fl = float;
using db = double;
using ld = long double;
using pii = std::pair<int, int>;
using pll = std::pair<long long, long long>;
using vi = std::vector<int>;
using vll = std::vector<long long>;
using vvi = std::vector<std::vector<int>>;
using vvll = std::vector<std::vector<long long>>;
using vvvi = std::vector<std::vector<std::vector<int>>>;
using vvvll = std::vector<std::vector<std::vector<long long>>>;
using vvvvi = std::vector<std::vector<std::vector<std::vector<int>>>>;
using vvvvll = std::vector<std::vector<std::vector<std::vector<long long>>>>;
using vb = std::basic_string<bool>;
using vvb = std::vector<std::basic_string<bool>>;
using vvvb = std::vector<std::vector<std::basic_string<bool>>>;
using vstr = std::vector<std::string>;
using vvstr = std::vector<std::vector<std::string>>;
using vvvstr = std::vector<std::vector<std::vector<std::string>>>;
using vpii = std::vector<std::pair<int, int>>;
using vpll = std::vector<std::pair<long long, long long>>;
using vvpii = std::vector<std::vector<std::pair<int, int>>>;
using vvpll = std::vector<std::vector<std::pair<long long, long long>>>;
using vvvpii = std::vector<std::vector<std::vector<std::pair<int, int>>>>;
using vvvpll = std::vector<std::vector<std::vector<std::pair<long long, long long>>>>;
using seti = std::set<int>;
using setll = std::set<long long>;
using vseti = std::vector<std::set<int>>;
using vsetll = std::vector<std::set<long long>>;
using vvseti = std::vector<std::vector<std::set<int>>>;
using vvsetll = std::vector<std::vector<std::set<long long>>>;
using mapii = std::map<int, int>;
using mapll = std::map<long long, long long>;
using vmapii = std::vector<std::map<int, int>>;
using vmapll = std::vector<std::map<long long, long long>>;
using vvmapii = std::vector<std::vector<std::map<int, int>>>;
using vvmapll = std::vector<std::vector<std::map<long long, long long>>>;
template<class T> using vec = std::vector<T>;
template<class T> using vec2 = std::vector<std::vector<T>>;
template<class T> using vec3 = std::vector<std::vector<std::vector<T>>>;
template<class T> using vec4 = std::vector<std::vector<std::vector<std::vector<T>>>>;
template<class T> using maxheap = std::priority_queue<T, std::vector<T>, std::less<T>>;
template<class T> using minheap = std::priority_queue<T, std::vector<T>, std::greater<T>>;

#define ALL(V)       std::begin(V), std::end(V)
#define RALL(V)      std::rbegin(V), std::rend(V)
#define ALLMID(V, n) std::begin(V), std::next(std::begin(V), n), std::end(V)
#define MIN(T)       (std::numeric_limits<T>::lowest())
#define MAX(T)       (std::numeric_limits<T>::max())
#define EXPR(...)    (([&]() __VA_ARGS__)())
#define LAMBDA(...)  ([&](const auto&... _args_) { return (__VA_ARGS__); })
#define ARG(idx)     (std::get<(idx)>(std::forward_as_tuple(_args_...)))

#if __cplusplus >= 202001U
#define REP_VAR_NAME(n)                   REP_VAR_NAME_(n)
#define REP_VAR_NAME_(n)                  variable_for_loop_##n
#define REP_OVERLOAD4(a, b, c, d, e, ...) e

#define REP1(N)              for ([[maybe_unused]] const auto REP_VAR_NAME(__LINE__) : std::views::iota(std::decay_t<decltype(N)>{}, N))
#define REP2(i, N)           for ([[maybe_unused]] const auto i : std::views::iota(std::decay_t<decltype(N)>{}, N))
#define REP3(i, A, B)        for ([[maybe_unused]] const auto i : std::views::iota(static_cast<std::common_type_t<decltype(A), decltype(B)>>(A), static_cast<std::common_type_t<decltype(A), decltype(B)>>(B)))
#define REP4(i, A, B, C)     for ([[maybe_unused]] std::common_type_t<decltype(A), decltype(B)> i = (A); std::less<decltype(i)>{}(i, (B)); i += (C))
#define REP1_REV(N)          for ([[maybe_unused]] const auto REP_VAR_NAME(__LINE__) : std::views::iota(std::decay_t<decltype(N)>{}, N) | std::views::reverse)
#define REP2_REV(i, N)       for ([[maybe_unused]] const auto i : std::views::iota(std::decay_t<decltype(N)>{}, N) | std::views::reverse)
#define REP3_REV(i, A, B)    for ([[maybe_unused]] const auto i : std::views::iota(static_cast<std::common_type_t<decltype(A), decltype(B)>>(A), static_cast<std::common_type_t<decltype(A), decltype(B)>>(B)) | std::views::reverse)
#define REP4_REV(i, A, B, C) for ([[maybe_unused]] std::common_type_t<decltype(A), decltype(B)> i = (B) -1; std::less<decltype(i)>{}((A) -1, i); i -= (C))
#define rep(...)             REP_OVERLOAD4(__VA_ARGS__, REP4, REP3, REP2, REP1)(__VA_ARGS__)
#define rrep(...)            REP_OVERLOAD4(__VA_ARGS__, REP4_REV, REP3_REV, REP2_REV, REP1_REV)(__VA_ARGS__)
#if __GNUC__ >= 12
#define repin(T, i, N) for ([[maybe_unused]] const auto i : std::views::istream<std::decay_t<T>>(std::cin) | std::views::take(N))
#endif
#else
#define rep(i, N)       for ([[maybe_unused]] auto i = std::decay_t<decltype(N)>{ 0 }; i != (N); ++i)
#define rrep(i, N)      for ([[maybe_unused]] auto i = (N) -1; i != -1; --i)
#define range(i, A, B)  for ([[maybe_unused]] auto i = (A); i != (B); ++i)
#define rrange(i, A, B) for ([[maybe_unused]] auto i = (B) -1; i != (A) -1; --i)
#endif
#include <unistd.h>
#include <immintrin.h>
// Thanks for https://zenn.dev/mizar/articles/fc87d667153080
class FastIstream : public std::ios_base {
    constexpr static int buffersize = (1 << 18) - 1;
    char buffer[buffersize + 1];
    char* cur = buffer;
    char* eof = buffer;
    inline void reload(ptrdiff_t w) {
        if (eof - w < cur) [[unlikely]] {
            if (eof == buffer + buffersize) [[likely]] {
                ptrdiff_t rem = eof - cur;
                std::memcpy(buffer, cur, rem);
                *(eof = buffer + rem + read(0, buffer + rem, buffersize - rem)) = '\0';
                cur = buffer;
            } else if (eof <= cur) {
                *(eof = buffer + read(0, buffer, buffersize)) = '\0';
                cur = buffer;
            }
        }
    }
public:
    FastIstream& operator>>(bool& n) {
        reload(2);
        n = *cur == '1';
        cur += 2;
        return *this;
    }
    FastIstream& operator>>(short& n) {
        reload(8);
        short neg = (*cur == '-') * -2 + 1;
        cur += neg == -1;
        uint64_t tmp = *(uint64_t*) cur ^ 0x3030303030303030u;
        int clz = std::countl_zero((tmp & 0x1010101010101010u) & (-(tmp & 0x1010101010101010u))) + 5;
        cur += (72 - clz) >> 3;
        tmp = ((tmp << clz) * 0xa01ull) >> 8 & 0x00ff00ff00ff00ffull;
        tmp = (tmp * 0x640001ull) >> 16 & 0x0000ffff0000ffffull;
        n = (short) ((tmp * 0x271000000001ull) >> 32) * neg;
        return *this;
    }
    FastIstream& operator>>(unsigned short& n) {
        reload(8);
        uint64_t tmp = *(uint64_t*) cur ^ 0x3030303030303030u;
        int clz = std::countl_zero((tmp & 0x1010101010101010u) & (-(tmp & 0x1010101010101010u))) + 5;
        cur += (72 - clz) >> 3;
        tmp = ((tmp << clz) * 0xa01ull) >> 8 & 0x00ff00ff00ff00ffull;
        tmp = (tmp * 0x640001ull) >> 16 & 0x0000ffff0000ffffull;
        n = (unsigned short) ((tmp * 0x271000000001ull) >> 32);
        return *this;
    }
    FastIstream& operator>>(unsigned int& n) {
        reload(16);
        uint64_t tmp = *(uint64_t*) cur ^ 0x3030303030303030u, tmp2 = tmp & 0x1010101010101010u;
        if (tmp2) {
            int clz = std::countl_zero(tmp2 & -tmp2) + 5;
            cur += (72 - clz) >> 3;
            tmp = ((tmp << clz) * 0xa01ull) >> 8 & 0x00ff00ff00ff00ffull;
            tmp = (tmp * 0x640001ull) >> 16 & 0x0000ffff0000ffffull;
            n = (unsigned) ((tmp * 0x271000000001ull) >> 32);
        } else {
            cur += 8;
            tmp = (tmp * 0xa01ull) >> 8 & 0x00ff00ff00ff00ffull;
            tmp = (tmp * 0x640001ull) >> 16 & 0x0000ffff0000ffffull;
            n = (unsigned) ((tmp * 0x271000000001ull) >> 32);
            if (char c = *(cur++); c >= '0') {
                n = 10 * n + (c - '0');
                if ((c = *(cur++)) >= '0') n = 10 * n + (c - '0'), ++cur;
            }
        }
        return *this;
    }
    FastIstream& operator>>(int& n) {
        reload(16);
        int neg = (*cur == '-') * -2 + 1;
        cur += neg == -1;
        uint64_t tmp = *(uint64_t*) cur ^ 0x3030303030303030u, tmp2 = tmp & 0x1010101010101010u;
        if (tmp2) {
            int clz = std::countl_zero(tmp2 & -tmp2) + 5;
            cur += (72 - clz) >> 3;
            tmp = ((tmp << clz) * 0xa01ull) >> 8 & 0x00ff00ff00ff00ffull;
            tmp = (tmp * 0x640001ull) >> 16 & 0x0000ffff0000ffffull;
            n = (int) ((tmp * 0x271000000001ull) >> 32);
        } else {
            cur += 8;
            tmp = (tmp * 0xa01ull) >> 8 & 0x00ff00ff00ff00ffull;
            tmp = (tmp * 0x640001ull) >> 16 & 0x0000ffff0000ffffull;
            n = (int) ((tmp * 0x271000000001ull) >> 32);
            if (char c = *(cur++); c >= '0') {
                n = 10 * n + (c - '0');
                if ((c = *(cur++)) >= '0') n = 10 * n + (c - '0'), ++cur;
            }
        }
        n *= neg;
        return *this;
    }
    FastIstream& operator>>(unsigned long long& n) {
        reload(32);
#ifndef __AVX512VL__
        n = 0;
        while (*cur >= '0') n = 10 * n + (*(cur++) - '0');
        ++cur;
#else
        unsigned long long tmp[3], tmp2[3];
        std::memcpy(tmp, cur, 24);
        int width;
        if ((tmp2[0] = (tmp[0] ^= 0x3030303030303030) & 0x1010101010101010)) [[unlikely]] {
            width = std::countr_zero(tmp2[0]) - 4;
            n = ((((((tmp[0] << (64 - width)) * 0xa01ull) >> 8 & 0x00ff00ff00ff00ffull) * 0x640001ull) >> 16 & 0x0000ffff0000ffffull) * 0x271000000001ull) >> 32;
            cur += (width >> 3) + 1;
        } else {
            __m256i tmp3;
            if ((tmp2[1] = (tmp[1] ^= 0x3030303030303030) & 0x1010101010101010)) [[unlikely]] {
                width = 60 + std::countr_zero(tmp2[1]);
                if (width == 64) [[unlikely]]
                    tmp3 = _mm256_setr_epi64x(0, 0, 0, tmp[0]);
                else tmp3 = _mm256_setr_epi64x(0, 0, tmp[0] << (128 - width), tmp[1] << (128 - width) | tmp[0] >> (width - 64));
            } else {
                width = 124 + std::countr_zero((tmp[2] ^= 0x3030303030303030) & 0x1010101010101010);
                if (width == 128) [[unlikely]]
                    tmp3 = _mm256_setr_epi64x(0, 0, tmp[0], tmp[1]);
                else tmp3 = _mm256_setr_epi64x(0, tmp[0] << (192 - width), tmp[1] << (192 - width) | tmp[0] >> (width - 128), tmp[2] << (192 - width) | tmp[1] >> (width - 128));
            }
            cur += (width >> 3) + 1;
            alignas(32) unsigned long long res[4];
            _mm256_store_epi64(res, _mm256_srli_epi64(_mm256_mullo_epi64(_mm256_srli_epi32(_mm256_mullo_epi32(_mm256_srli_epi16(_mm256_mullo_epi16(_mm256_and_si256(tmp3, _mm256_set1_epi8(0x0f)), _mm256_set1_epi16(0xa01)), 8), _mm256_set1_epi32(0x640001)), 16), _mm256_set1_epi64x(0x271000000001)), 32));
            n = res[1] * 10000000000000000 + res[2] * 100000000 + res[3];
        }
#endif
        return *this;
    }
    FastIstream& operator>>(long long& n) {
        reload(32);
        long long neg = (*cur == '-') * -2 + 1;
        cur += neg == -1;
#ifndef __AVX512VL__
        n = 0;
        while (*cur >= '0') n = 10 * n + (*(cur++) - '0');
        ++cur;
        n *= neg;
#else
        unsigned long long tmp[3], tmp2[3];
        std::memcpy(tmp, cur, 24);
        int width;
        if ((tmp2[0] = (tmp[0] ^= 0x3030303030303030) & 0x1010101010101010)) [[unlikely]] {
            width = std::countr_zero(tmp2[0]) - 4;
            n = neg * (((((((tmp[0] << (64 - width)) * 0xa01ull) >> 8 & 0x00ff00ff00ff00ffull) * 0x640001ull) >> 16 & 0x0000ffff0000ffffull) * 0x271000000001ull) >> 32);
            cur += (width >> 3) + 1;
        } else {
            __m256i tmp3;
            if ((tmp2[1] = (tmp[1] ^= 0x3030303030303030) & 0x1010101010101010)) [[unlikely]] {
                width = 60 + std::countr_zero(tmp2[1]);
                if (width == 64) [[unlikely]]
                    tmp3 = _mm256_setr_epi64x(0, 0, 0, tmp[0]);
                else tmp3 = _mm256_setr_epi64x(0, 0, tmp[0] << (128 - width), tmp[1] << (128 - width) | tmp[0] >> (width - 64));
            } else {
                width = 124 + std::countr_zero((tmp[2] ^= 0x3030303030303030) & 0x1010101010101010);
                if (width == 128) [[unlikely]]
                    tmp3 = _mm256_setr_epi64x(0, 0, tmp[0], tmp[1]);
                else tmp3 = _mm256_setr_epi64x(0, tmp[0] << (192 - width), tmp[1] << (192 - width) | tmp[0] >> (width - 128), tmp[2] << (192 - width) | tmp[1] >> (width - 128));
            }
            cur += (width >> 3) + 1;
            alignas(32) long long res[4];
            _mm256_store_epi64(res, _mm256_srli_epi64(_mm256_mullo_epi64(_mm256_srli_epi32(_mm256_mullo_epi32(_mm256_srli_epi16(_mm256_mullo_epi16(_mm256_and_si256(tmp3, _mm256_set1_epi8(0x0f)), _mm256_set1_epi16(0xa01)), 8), _mm256_set1_epi32(0x640001)), 16), _mm256_set1_epi64x(0x271000000001)), 32));
            n = neg * (res[1] * 10000000000000000 + res[2] * 100000000 + res[3]);
        }
#endif
        return *this;
    }
    FastIstream& operator>>(long& n) {
        long long x;
        operator>>(x);
        n = x;
        return *this;
    }
    FastIstream& operator>>(unsigned long& n) {
        unsigned long long x;
        operator>>(x);
        n = x;
        return *this;
    }
    friend FastIstream& operator>>(FastIstream& is, char& c) {
        is.reload(2);
        c = *is.cur;
        is.cur += 2;
        return is;
    }
    friend FastIstream& operator>>(FastIstream& is, unsigned char& c) {
        is.reload(2);
        c = *is.cur;
        is.cur += 2;
        return is;
    }
    friend FastIstream& operator>>(FastIstream& is, signed char& c) {
        is.reload(2);
        c = *is.cur;
        is.cur += 2;
        return is;
    }
    friend FastIstream& operator>>(FastIstream& is, char* s) {
        while (true) {
            while (*is.cur > ' ' && is.cur != is.eof) *(s++) = *is.cur, ++is.cur;
            if (is.cur == is.eof) is.reload(is.buffersize);
            else break;
        }
        ++is.cur;
        *s = '\0';
        return is;
    }
    friend FastIstream& operator>>(FastIstream& is, std::string& s) {
        s.clear();
        while (true) {
            char* st = is.cur;
            while (*is.cur > ' ' && is.cur != is.eof) ++is.cur;
            s += std::string_view(st, is.cur - st);
            if (is.cur == is.eof) is.reload(is.buffersize);
            else break;
        }
        ++is.cur;
        return is;
    }
    FastIstream& operator>>(float& f) {
        std::string s;
        (*this) >> s;
        std::from_chars(s.c_str(), s.c_str() + s.length(), f);
        return *this;
    }
    FastIstream& operator>>(double& f) {
        std::string s;
        (*this) >> s;
        std::from_chars(s.c_str(), s.c_str() + s.length(), f);
        return *this;
    }
    FastIstream& operator>>(long double& f) {
        std::string s;
        (*this) >> s;
        std::from_chars(s.c_str(), s.c_str() + s.length(), f);
        return *this;
    }
    template<std::ranges::range T> friend FastIstream& operator>>(FastIstream& is, T& x) {
        for (auto& v : x) is >> v;
        return is;
    }
} fin;
class FastOstream : public std::ios_base {
    constexpr static int buffersize = 1 << 18;
    char buffer[buffersize];
    char* cur = buffer;
    inline void reload(ptrdiff_t w) {
        if (buffer + buffersize - w < cur) [[unlikely]] {
            [[maybe_unused]] int r = write(1, buffer, cur - buffer);
            cur = buffer;
        }
    }
    constexpr static std::array<unsigned, 10000> strtable = []() {
        std::array<unsigned, 10000> res;
        for (unsigned i = 0; i < 10000; ++i) {
            unsigned tmp[4];
            unsigned n = i;
            tmp[3] = (n % 10 + '0') << 24, n /= 10;
            tmp[2] = (n % 10 + '0') << 16, n /= 10;
            tmp[1] = (n % 10 + '0') << 8, n /= 10;
            tmp[0] = n % 10 + '0';
            res[i] = tmp[0] + tmp[1] + tmp[2] + tmp[3];
        }
        return res;
    }();
    constexpr static std::array<unsigned, 10000> strtable2 = []() {
        std::array<unsigned, 10000> res;
        for (unsigned i = 0; i < 10000; ++i) {
            unsigned tmp[4];
            unsigned n = i;
            if (i < 10) n *= 1000;
            else if (i < 100) n *= 100;
            else if (i < 1000) n *= 10;
            tmp[3] = (n % 10 + '0') << 24, n /= 10;
            tmp[2] = (n % 10 + '0') << 16, n /= 10;
            tmp[1] = (n % 10 + '0') << 8, n /= 10;
            tmp[0] = n % 10 + '0';
            res[i] = tmp[0] + tmp[1] + tmp[2] + tmp[3];
        }
        return res;
    }();
    template<class T> void putfloat(T f) {
        bool fixed = flags() & std::ios_base::fixed;
        bool scientific = flags() & std::ios_base::scientific;
        bool uppercase = flags() & std::ios_base::uppercase;
        if (fixed && scientific && (flags() & std::ios_base::showbase)) {
            std::memcpy(cur, (uppercase ? "0X" : "0x"), 2);
            cur += 2;
        }
        std::chars_format fmt = (fixed ? (scientific ? std::chars_format::hex : std::chars_format::fixed) : (scientific ? std::chars_format::scientific : std::chars_format::general));
        auto conv = [&]() {
            return std::to_chars(cur, buffer + buffersize, f, fmt, precision());
        };
        auto [ptr, ec] = conv();
        char* p;
        if (ec == std::errc::value_too_large) {
            reload(buffersize);
            p = cur;
            cur = conv().ptr;
        } else p = cur, cur = ptr;
        if (uppercase) {
            while (p != cur) {
                if (*p > '9') *p -= ('a' - 'A');
                ++p;
            }
        }
    }
public:
    FastOstream() {
        precision(6);
        setf(std::ios_base::showbase);
    }
    ~FastOstream() { reload(buffersize); }
    FastOstream& flush() {
        reload(buffersize);
        return *this;
    }
    char widen(char c) const { return c; }
    FastOstream& put(char c) {
        reload(1);
        *(cur++) = c;
        return *this;
    }
    FastOstream& operator<<(std::basic_ostream<FastOstream, void>& (*pf)(std::basic_ostream<FastOstream, void>&) );
    FastOstream& operator<<(std::basic_ios<FastOstream, void>& (*pf)(std::basic_ios<FastOstream, void>&) );
    FastOstream& operator<<(std::ios_base& (*pf)(std::ios_base&) ) {
        pf(*this);
        return *this;
    }
    FastOstream& operator<<(bool n) {
        if (ios_base::flags() & std::ios_base::boolalpha) {
            if (n) {
                reload(4);
                std::memcpy(cur, "true", 4);
                cur += 4;
            } else {
                reload(5);
                std::memcpy(cur, "false", 5);
                cur += 5;
            }
        } else {
            reload(1);
            *(cur++) = '0' + n;
        }
        return *this;
    }
    FastOstream& operator<<(unsigned short n) {
        reload(5);
        if (n >= 10000) {
            *(cur++) = '0' + n / 10000, n %= 10000;
            *reinterpret_cast<unsigned*>(cur) = strtable[n];
            cur += 4;
        } else if (n >= 1000) {
            *reinterpret_cast<unsigned*>(cur) = strtable[n];
            cur += 4;
        } else if (n >= 100) {
            *reinterpret_cast<unsigned*>(cur) = strtable[n * 10];
            cur += 3;
        } else if (n >= 10) {
            *(cur++) = '0' + n / 10;
            *(cur++) = '0' + n % 10;
        } else *(cur++) = '0' + n;
        return *this;
    }
    FastOstream& operator<<(short n) {
        reload(6);
        if (n < 0) *(cur++) = '-', n = -n;
        if (n >= 10000) {
            *(cur++) = '0' + n / 10000, n %= 10000;
            *reinterpret_cast<unsigned*>(cur) = strtable[n];
            cur += 4;
        } else if (n >= 1000) {
            *reinterpret_cast<unsigned*>(cur) = strtable[n];
            cur += 4;
        } else if (n >= 100) {
            *reinterpret_cast<unsigned*>(cur) = strtable[n * 10];
            cur += 3;
        } else if (n >= 10) {
            *reinterpret_cast<unsigned*>(cur) = strtable[n * 100];
            cur += 2;
        } else *(cur++) = '0' + n;
        return *this;
    }
    FastOstream& operator<<(unsigned n) {
        reload(10);
        unsigned long long buf = 0;
        char d = 0;
        if (n >= 100000000) {
            d = 8;
            buf = static_cast<unsigned long long>(strtable[n % 10000]) << 32 | strtable[(n / 10000) % 10000];
            n /= 100000000;
        } else if (n >= 10000) {
            d = 4;
            buf = strtable[n % 10000];
            n /= 10000;
        }
        *reinterpret_cast<unsigned*>(cur) = strtable2[n];
        cur += (n >= 10) + (n >= 100) + (n >= 1000) + 1;
        *reinterpret_cast<unsigned long long*>(cur) = buf;
        cur += d;
        return *this;
    }
    FastOstream& operator<<(int n) {
        reload(11);
        if (n < 0) *(cur++) = '-', n = -n;
        unsigned long long buf = 0;
        char d = 0;
        if (n >= 100000000) {
            d = 8;
            buf = static_cast<unsigned long long>(strtable[n % 10000]) << 32 | strtable[(n / 10000) % 10000];
            n /= 100000000;
        } else if (n >= 10000) {
            d = 4;
            buf = strtable[n % 10000];
            n /= 10000;
        }
        *reinterpret_cast<unsigned*>(cur) = strtable2[n];
        cur += (n >= 10) + (n >= 100) + (n >= 1000) + 1;
        *reinterpret_cast<unsigned long long*>(cur) = buf;
        cur += d;
        return *this;
    }
    FastOstream& operator<<(unsigned long long n) {
        reload(20);
        static unsigned buf[4];
        int d = 0;
        if (n >= 10000000000000000) {
            d = 16;
            buf[3] = strtable[n % 10000], n /= 10000;
            buf[2] = strtable[n % 10000], n /= 10000;
            buf[1] = strtable[n % 10000], n /= 10000;
            buf[0] = strtable[n % 10000], n /= 10000;
        } else if (n >= 1000000000000) {
            d = 12;
            buf[2] = strtable[n % 10000], n /= 10000;
            buf[1] = strtable[n % 10000], n /= 10000;
            buf[0] = strtable[n % 10000], n /= 10000;
        } else if (n >= 100000000) {
            d = 8;
            buf[1] = strtable[n % 10000], n /= 10000;
            buf[0] = strtable[n % 10000], n /= 10000;
        } else if (n >= 10000) {
            d = 4;
            buf[0] = strtable[n % 10000], n /= 10000;
        }
        *(unsigned*) cur = strtable2[n];
        cur += (n >= 10) + (n >= 100) + (n >= 1000) + 1;
        std::memcpy(cur, buf, d);
        cur += d;
        return *this;
    }
    FastOstream& operator<<(long long n) {
        reload(21);
        if (n < 0) *(cur++) = '-', n = -n;
        static unsigned buf[4];
        char d = 0;
        if (n >= 10000000000000000) {
            d = 16;
            buf[3] = strtable[n % 10000], n /= 10000;
            buf[2] = strtable[n % 10000], n /= 10000;
            buf[1] = strtable[n % 10000], n /= 10000;
            buf[0] = strtable[n % 10000], n /= 10000;
        } else if (n >= 1000000000000) {
            d = 12;
            buf[2] = strtable[n % 10000], n /= 10000;
            buf[1] = strtable[n % 10000], n /= 10000;
            buf[0] = strtable[n % 10000], n /= 10000;
        } else if (n >= 100000000) {
            d = 8;
            buf[1] = strtable[n % 10000], n /= 10000;
            buf[0] = strtable[n % 10000], n /= 10000;
        } else if (n >= 10000) {
            d = 4;
            buf[0] = strtable[n % 10000], n /= 10000;
        }
        *(unsigned*) cur = strtable2[n];
        cur += (n >= 10) + (n >= 100) + (n >= 1000) + 1;
        std::memcpy(cur, buf, d);
        cur += d;
        return *this;
    }
    FastOstream& operator<<(long n) { return operator<<(static_cast<long long>(n)); }
    FastOstream& operator<<(unsigned long n) { return operator<<(static_cast<unsigned long long>(n)); }
    FastOstream& operator<<(float f) {
        reload(16);
        putfloat(f);
        return *this;
    }
    FastOstream& operator<<(double f) {
        reload(32);
        putfloat(f);
        return *this;
    }
    FastOstream& operator<<(long double f) {
        reload(64);
        putfloat(f);
        return *this;
    }
    FastOstream& operator<<(const void* p) {
        reload(18);
        if (flags() & std::ios_base::showbase) {
            *cur = '0';
            *(cur + 1) = flags() & std::ios_base::uppercase ? 'X' : 'x';
            cur += 2;
        }
        cur = std::to_chars(cur, buffer + buffersize, reinterpret_cast<unsigned long long>(p), 16).ptr;
        return *this;
    }
    FastOstream& operator<<(std::nullptr_t) {
        reload(7);
        std::memcpy(cur, "nullptr", 7);
        cur += 7;
        return *this;
    }
    friend FastOstream& operator<<(FastOstream& os, char c) {
        os.reload(1);
        *(os.cur++) = c;
        return os;
    }
    friend FastOstream& operator<<(FastOstream& os, signed char c) {
        os.reload(1);
        *(os.cur++) = c;
        return os;
    }
    friend FastOstream& operator<<(FastOstream& os, unsigned char c) {
        os.reload(1);
        *(os.cur++) = c;
        return os;
    }
    friend FastOstream& operator<<(FastOstream& os, const char* s) {
        size_t n = std::strlen(s);
        if (n >= os.buffersize) {
            os.reload(buffersize);
            write(1, s, n);
        } else {
            os.reload(n);
            std::memcpy(os.cur, s, n);
            os.cur += n;
        }
        return os;
    }
    friend FastOstream& operator<<(FastOstream& os, const std::string& s) {
        size_t n = s.length();
        if (n >= os.buffersize) {
            os.reload(buffersize);
            write(1, s.data(), n);
        } else {
            os.reload(n);
            std::memcpy(os.cur, s.data(), n);
            os.cur += n;
        }
        return os;
    }
    friend FastOstream& operator<<(FastOstream& os, std::string_view s) {
        size_t n = s.length();
        if (n >= os.buffersize) {
            os.reload(buffersize);
            write(1, s.data(), n);
        } else {
            os.reload(n);
            std::memcpy(os.cur, s.data(), n);
            os.cur += n;
        }
        return os;
    }
    template<std::ranges::range T> friend FastOstream& operator<<(FastOstream& os, const T& v) {
        size_t n = std::distance(std::ranges::begin(v), std::ranges::end(v)), cnt = 0;
        for (const auto& x : v) {
            os << x;
            if (++cnt != n) os << ' ';
        }
        return os;
    }
#if __GNUC__ >= 6
    friend FastOstream& operator<<(FastOstream& os, std::_Setprecision prec) {
        os.precision(prec._M_n);
        return os;
    }
#endif
} fout;
namespace std {
template<> class basic_ios<FastOstream, void> {
protected:
    FastOstream& ref;
public:
    basic_ios(FastOstream& r) : ref(r) {}
    char widen(char c) { return ref.widen(c); }
};
template<> class basic_ostream<FastOstream, void> : public basic_ios<FastOstream, void> {
public:
    basic_ostream(FastOstream& r) : basic_ios(r) {}
    basic_ostream& put(char c) {
        basic_ios::ref.put(c);
        return *this;
    }
    basic_ostream& flush() {
        basic_ios::ref.flush();
        return *this;
    }
};
}  // namespace std
FastOstream& FastOstream::operator<<(std::basic_ostream<FastOstream, void>& (*pf)(std::basic_ostream<FastOstream, void>&) ) {
    std::basic_ostream<FastOstream, void> tmp(*this);
    pf(tmp);
    return *this;
}
FastOstream& FastOstream::operator<<(std::basic_ios<FastOstream, void>& (*pf)(std::basic_ios<FastOstream, void>&) ) {
    std::basic_ios<FastOstream, void> tmp(*this);
    pf(tmp);
    return *this;
}
template<class T> class ModintTraits : public T {
    using base_type = T;
public:
    using value_type = std::decay_t<decltype(base_type::mod())>;
    using modint_type = ModintTraits;
    constexpr static bool is_staticmod = !requires { base_type::set_mod(0); };
    constexpr ModintTraits() noexcept : T() {}
    template<class U> constexpr ModintTraits(U x) noexcept { operator=(x); }
    constexpr explicit operator value_type() const noexcept { return val(); }
    constexpr static void set_mod(value_type x) {
        static_assert(!is_staticmod, "ModintTraits::set_mod / Mod must be dynamic.");
        if (x <= 1) throw std::runtime_error("ModintTraits::set_mod / Mod must be at least 2.");
        if (x == mod()) return;
        base_type::set_mod(x);
    }
    constexpr value_type val() const noexcept { return base_type::val(); }
    constexpr static value_type mod() noexcept { return base_type::mod(); }
    template<class U> constexpr modint_type& operator=(U x) noexcept {
        static_assert(std::is_integral_v<U>, "ModintTraits::operator= / Only integer types can be assigned.");
        if constexpr (std::is_unsigned_v<U>) {
            if constexpr (std::is_same_v<U, unsigned long long> || std::is_same_v<U, unsigned long>) base_type::assign(static_cast<std::uint64_t>(x));
            else base_type::assign(static_cast<std::uint32_t>(x));
        } else {
            if (x < 0) {
                if constexpr (std::is_same_v<U, long long> || std::is_same_v<U, long>) base_type::assign(static_cast<std::uint64_t>(-x));
                else base_type::assign(static_cast<std::uint32_t>(-x));
                base_type::neg();
            } else {
                if constexpr (std::is_same_v<U, long long> || std::is_same_v<U, long>) base_type::assign(static_cast<std::uint64_t>(x));
                else base_type::assign(static_cast<std::uint32_t>(x));
            }
        }
        return *this;
    }
    constexpr static modint_type raw(value_type x) noexcept {
        modint_type res;
        res.rawassign(x);
        return res;
    }
    template<class Istream> friend Istream& operator>>(Istream& ist, modint_type& x) {
        value_type n;
        ist >> n;
        x = n;
        return ist;
    }
    template<class Ostream> friend Ostream& operator<<(Ostream& ost, modint_type x) { return ost << x.val(); }
    constexpr modint_type inv() const {
        value_type a = 1, b = 0, x = val(), y = mod();
        if (x == 0) throw std::runtime_error("ModintTraits::inv / Zero division is not possible.");
        while (true) {
            if (x <= 1) {
                if (x == 0) [[unlikely]]
                    break;
                else return modint_type::raw(a);
            }
            b += a * (y / x);
            y %= x;
            if (y <= 1) {
                if (y == 0) [[unlikely]]
                    break;
                else return modint_type::raw(mod() - b);
            }
            a += b * (x / y);
            x %= y;
        }
        throw std::runtime_error("ModintTraits::inv / Cannot calculate inverse element.");
    }
    constexpr modint_type pow(uint64_t e) const noexcept {
        modint_type res = modint_type::raw(1), pow = *this;
        while (e) {
            modint_type tmp = pow * pow;
            if (e & 1) res *= pow;
            pow = tmp;
            e >>= 1;
        }
        return res;
    }
    constexpr modint_type operator+() const noexcept { return *this; }
    constexpr modint_type operator-() const noexcept {
        modint_type res = *this;
        res.neg();
        return res;
    }
    constexpr modint_type& operator++() noexcept {
        base_type::inc();
        return *this;
    }
    constexpr modint_type& operator--() noexcept {
        base_type::dec();
        return *this;
    }
    constexpr modint_type operator++(int) noexcept {
        modint_type copy = *this;
        operator++();
        return copy;
    }
    constexpr modint_type operator--(int) noexcept {
        modint_type copy = *this;
        operator--();
        return copy;
    }
    constexpr modint_type& operator+=(modint_type x) noexcept {
        base_type::add(x);
        return *this;
    }
    constexpr modint_type& operator-=(modint_type x) noexcept {
        base_type::sub(x);
        return *this;
    }
    constexpr modint_type& operator*=(modint_type x) noexcept {
        base_type::mul(x);
        return *this;
    }
    constexpr modint_type& operator/=(modint_type x) {
        operator*=(x.inv());
        return *this;
    }
    friend constexpr modint_type operator+(modint_type l, modint_type r) noexcept { return modint_type(l) += r; }
    friend constexpr modint_type operator-(modint_type l, modint_type r) noexcept { return modint_type(l) -= r; }
    friend constexpr modint_type operator*(modint_type l, modint_type r) noexcept { return modint_type(l) *= r; }
    friend constexpr modint_type operator/(modint_type l, modint_type r) { return modint_type(l) /= r; }
    friend constexpr bool operator==(modint_type l, modint_type r) noexcept { return l.val() == r.val(); }
    friend constexpr bool operator!=(modint_type l, modint_type r) noexcept { return l.val() != r.val(); }
    constexpr int legendre() const noexcept {
        value_type res = pow((mod() - 1) >> 1).val();
        return (res <= 1 ? static_cast<int>(res) : -1);
    }
    constexpr int jacobi() const noexcept {
        value_type a = val(), n = mod();
        if (a == 1) return 1;
        if (std::gcd(a, n) != 1) return 0;
        int res = 1;
        while (a != 0) {
            while (!(a & 1) && a != 0) {
                a >>= 1;
                if ((n & 0b111) == 3 || (n & 0b111) == 5) res = -res;
            }
            if ((a & 0b11) == 3 || (n & 0b11) == 3) res = -res;
            std::swap(a, n);
            a %= n;
        }
        if (n != 1) return 0;
        return res;
    }
    constexpr modint_type sqrt() const noexcept {
        const value_type vl = val(), md = mod();
        if (vl <= 1) return *this;
        auto get_min = [](modint_type x) {
            return x.val() > (mod() >> 1) ? -x : x;
        };
        if ((md & 0b11) == 3) return get_min(pow((md + 1) >> 2));
        else if ((md & 0b111) == 5) {
            modint_type res = pow((md + 3) >> 3);
            if constexpr (is_staticmod) {
                constexpr modint_type p = modint_type::raw(2).pow((md - 1) >> 2);
                res *= p;
            } else if (res * res != *this) res *= modint_type::raw(2).pow((md - 1) >> 2);
            return get_min(res);
        } else {
            value_type Q = md - 1;
            uint32_t S = 0;
            while ((Q & 1) == 0) Q >>= 1, ++S;
            if (std::countr_zero(md - 1) < 6) {
                modint_type z = modint_type::raw(1);
                while (z.legendre() != -1) ++z;
                modint_type t = pow(Q), R = pow((Q + 1) / 2);
                if (t.val() == 1) return R;
                uint32_t M = S;
                modint_type c = z.pow(Q);
                do {
                    modint_type U = t * t;
                    uint32_t i = 1;
                    while (U.val() != 1) U = U * U, ++i;
                    modint_type b = c;
                    for (uint32_t j = 0; j < (M - i - 1); ++j) b *= b;
                    M = i, c = b * b, t *= c, R *= b;
                } while (t.val() != 1);
                return get_min(R);
            } else {
                modint_type a = 1;
                while ((a * a - *this).legendre() != -1) ++a;
                modint_type res1 = modint_type::raw(1), res2, pow1 = a, pow2 = modint_type::raw(1), w = a * a - *this;
                value_type e = (md + 1) / 2;
                while (true) {
                    if (e & 1) {
                        modint_type tmp = res1;
                        res1 = res1 * pow1 + res2 * pow2 * w;
                        res2 = tmp * pow2 + res2 * pow1;
                    }
                    e >>= 1;
                    if (e == 0) return get_min(res1);
                    modint_type tmp = pow1;
                    pow1 = pow1 * pow1 + pow2 * pow2 * w;
                    pow2 *= modint_type::raw(2) * tmp;
                }
            }
        }
    }
};
template<std::uint32_t mod_> class StaticModint32_impl {
    using value_type = std::uint32_t;
    using modint_type = StaticModint32_impl;
    value_type val_ = 0;
protected:
    constexpr StaticModint32_impl() noexcept {}
    constexpr value_type val() const noexcept { return val_; }
    static constexpr value_type mod() noexcept { return mod_; }
    constexpr void assign(std::uint32_t x) noexcept { val_ = x % mod_; }
    constexpr void assign(std::uint64_t x) noexcept { val_ = x % mod_; }
    constexpr void rawassign(value_type x) noexcept { val_ = x; }
    constexpr void neg() noexcept { val_ = (val_ == 0 ? 0 : mod_ - val_); }
    constexpr void inc() noexcept { val_ = (val_ == mod_ - 1 ? 0 : val_ + 1); }
    constexpr void dec() noexcept { val_ = (val_ == 0 ? mod_ - 1 : val_ - 1); }
    constexpr void add(modint_type x) noexcept {
        if (mod_ - val_ > x.val_) val_ += x.val_;
        else val_ = x.val_ - (mod_ - val_);
    }
    constexpr void sub(modint_type x) noexcept {
        if (val_ >= x.val_) val_ -= x.val_;
        else val_ = mod_ - (x.val_ - val_);
    }
    constexpr void mul(modint_type x) noexcept { val_ = static_cast<std::uint64_t>(val_) * x.val_ % mod_; }
};
template<std::uint32_t mod_ = 998244353> using StaticModint32 = ModintTraits<StaticModint32_impl<mod_>>;
template<std::uint64_t mod_> class StaticModint64_impl {
    using value_type = std::uint64_t;
    using modint_type = StaticModint64_impl;
    value_type val_ = 0;
protected:
    constexpr StaticModint64_impl() noexcept {}
    constexpr value_type val() const noexcept { return val_; }
    static constexpr value_type mod() noexcept { return mod_; }
    constexpr void assign(std::uint32_t x) noexcept {
        if constexpr (mod_ < (1ull << 32)) val_ = x % mod_;
        else val_ = x;
    }
    constexpr void assign(std::uint64_t x) noexcept { val_ = x % mod_; }
    constexpr void rawassign(value_type x) noexcept { val_ = x; }
    constexpr void neg() noexcept { val_ = (val_ == 0 ? 0 : mod_ - val_); }
    constexpr void inc() noexcept { val_ = (val_ == mod_ - 1 ? 0 : val_ + 1); }
    constexpr void dec() noexcept { val_ = (val_ == 0 ? mod_ - 1 : val_ - 1); }
    constexpr void add(modint_type x) noexcept {
        if (mod_ - val_ > x.val_) val_ += x.val_;
        else val_ = x.val_ - (mod_ - val_);
    }
    constexpr void sub(modint_type x) noexcept {
        if (val_ >= x.val_) val_ -= x.val_;
        else val_ = mod_ - (x.val_ - val_);
    }
    constexpr void mul(modint_type x) noexcept { val_ = static_cast<__uint128_t>(val_) * x.val_ % mod_; }
};
template<std::uint64_t mod_ = 998244353> using StaticModint64 = ModintTraits<StaticModint64_impl<mod_>>;
template<std::uint64_t mod_ = 998244353> using StaticModint = std::conditional_t<(mod_ < (1ull << 32)), StaticModint32<mod_>, StaticModint64<mod_>>;
template<int id> class DynamicModint32_impl {
    using value_type = std::uint32_t;
    using modint_type = DynamicModint32_impl;
    static inline value_type mod_ = 0;
    static inline std::uint64_t mod64_ = 0;
    static inline __uint128_t L_ = 0;
    value_type val_ = 0;
    value_type reduce(std::uint32_t c) const noexcept {
        std::uint32_t q = (c * L_) >> 96;
        return c - q * mod_;
    }
    value_type reduce(std::uint64_t c) const noexcept {
        std::uint64_t q = (c * L_) >> 96;
        return c - q * mod64_;
    }
protected:
    DynamicModint32_impl() noexcept {}
    static void set_mod(value_type newmod) noexcept {
        mod_ = newmod, mod64_ = newmod;
        L_ = ((__uint128_t(1) << 96) - 1) / mod_ + 1;
    }
    value_type val() const noexcept { return val_; }
    static value_type mod() noexcept { return mod_; }
    void assign(std::uint32_t x) noexcept { val_ = reduce(x); }
    void assign(std::uint64_t x) noexcept { val_ = reduce(x); }
    void rawassign(value_type x) noexcept { val_ = x; }
    void neg() noexcept { val_ = (val_ == 0 ? 0 : mod_ - val_); }
    void inc() noexcept { val_ = (val_ == mod_ - 1 ? 0 : val_ + 1); }
    void dec() noexcept { val_ = (val_ == 0 ? mod_ - 1 : val_ - 1); }
    void add(modint_type x) noexcept {
        if (mod_ - val_ > x.val_) val_ += x.val_;
        else val_ = x.val_ - (mod_ - val_);
    }
    void sub(modint_type x) noexcept {
        if (val_ >= x.val_) val_ -= x.val_;
        else val_ = mod_ - (x.val_ - val_);
    }
    void mul(modint_type x) noexcept { val_ = reduce(static_cast<std::uint64_t>(val_) * x.val_); }
};
template<int id = 0> using DynamicModint32 = ModintTraits<DynamicModint32_impl<id>>;
template<int id> class DynamicModint64_impl {
    using value_type = std::uint64_t;
    using modint_type = DynamicModint64_impl;
    static inline value_type mod_ = 0;
    static inline __uint128_t mod128_ = 0, M_ = 0;
    value_type val_ = 0;
protected:
    DynamicModint64_impl() noexcept {}
    static void set_mod(value_type newmod) noexcept {
        mod_ = newmod, mod128_ = mod_;
        M_ = std::numeric_limits<__uint128_t>::max() / mod_ + std::has_single_bit(mod_);
    }
    value_type val() const noexcept { return val_; }
    static value_type mod() noexcept { return mod_; }
    void assign(std::uint64_t x) noexcept { val_ = x % mod_; }
    void rawassign(value_type x) noexcept { val_ = x; }
    void neg() noexcept { val_ = (val_ == 0 ? 0 : mod_ - val_); }
    void inc() noexcept { val_ = (val_ == mod_ - 1 ? 0 : val_ + 1); }
    void dec() noexcept { val_ = (val_ == 0 ? mod_ - 1 : val_ - 1); }
    void add(modint_type x) noexcept {
        if (mod_ - val_ > x.val_) val_ += x.val_;
        else val_ = x.val_ - (mod_ - val_);
    }
    void sub(modint_type x) noexcept {
        if (val_ >= x.val_) val_ -= x.val_;
        else val_ = mod_ - (x.val_ - val_);
    }
    void mul(modint_type x) noexcept {
        std::uint64_t tmp = static_cast<__uint128_t>(val_) * x.val_ - ((((M_ * val_) >> 64) * x.val_) >> 64) * mod128_;
        val_ = (tmp < mod_ ? tmp : tmp - mod_);
    }
};
template<int id = 0> using DynamicModint64 = ModintTraits<DynamicModint64_impl<id>>;
template<class Modint> class ModManager {
    Modint::value_type prev;
public:
    ModManager() { prev = Modint::mod(); }
    ~ModManager() {
        if (prev != 0) Modint::set_mod(prev);
    }
    void set_mod(Modint::value_type newmod) { Modint::set_mod(newmod); }
};
template<bool trial_division = true> bool isPrime32(const std::uint32_t x) {
    if constexpr (trial_division) {
        if (x % 2 == 0 || x % 3 == 0 || x % 5 == 0 || x % 7 == 0 || x % 11 == 0 || x % 13 == 0 || x % 17 == 0 || x % 19 == 0 || x % 23 == 0 || x % 29 == 0 || x % 31 == 0 || x % 37 == 0 || x % 41 == 0 || x % 43 == 0) return x <= 43 && (x == 2 || x == 3 || x == 5 || x == 7 || x == 11 || x == 13 || x == 17 || x == 19 || x == 23 || x == 29 || x == 31 || x == 37 || x == 41 || x == 43);
        if (x < 47 * 47) return (x > 1);
    } else {
        if (x % 2 == 0 || x % 3 == 0 || x % 5 == 0 || x % 7 == 0) return x <= 7 && (x == 2 || x == 3 || x == 5 || x == 7);
        if (x < 11 * 11) return (x > 1);
    }
    constexpr std::uint16_t bases[] = { 15591, 2018,  166,  7429, 8064, 16045, 10503, 4399,  1949, 1295,  2776, 3620, 560,   3128, 5212, 2657, 2300, 2021, 4652, 1471, 9336,  4018, 2398,  20462, 10277, 8028,  2213, 6219,  620,  3763,  4852, 5012,  3185,  1333, 6227, 5298, 1074, 2391,  5113, 7061, 803,  1269, 3875, 422,   751,  580,   4729,  10239, 746,  2951, 556,  2206, 3778, 481,   1522, 3476, 481,  2487, 3266, 5633,  488,   3373,  6441,  3344,
                                        17,    15105, 1490, 4154, 2036, 1882,  1813,  467,   3307, 14042, 6371, 658,  1005,  903,  737,  1887, 7447, 1888, 2848, 1784, 7559,  3400, 951,   13969, 4304,  177,   41,   19875, 3110, 13221, 8726, 571,   7043,  6943, 1199, 352,  6435, 165,   1169, 3315, 978,  233,  3003, 2562,  2994, 10587, 10030, 2377,  1902, 5354, 4447, 1555, 263,  27027, 2283, 305,  669,  1912, 601,  6186,  429,   1930,  14873, 1784,
                                        1661,  524,   3577, 236,  2360, 6146,  2850,  55637, 1753, 4178,  8466, 222,  2579,  2743, 2031, 2226, 2276, 374,  2132, 813,  23788, 1610, 4422,  5159,  1725,  3597,  3366, 14336, 579,  165,   1375, 10018, 12616, 9816, 1371, 536,  1867, 10864, 857,  2206, 5788, 434,  8085, 17618, 727,  3639,  1595,  4944,  2129, 2029, 8195, 8344, 6232, 9183,  8126, 1870, 3296, 7455, 8947, 25017, 541,   19115, 368,   566,
                                        5674,  411,   522,  1027, 8215, 2050,  6544,  10049, 614,  774,   2333, 3007, 35201, 4706, 1152, 1785, 1028, 1540, 3743, 493,  4474,  2521, 26845, 8354,  864,   18915, 5465, 2447,  42,   4511,  1660, 166,   1249,  6259, 2553, 304,  272,  7286,  73,   6554, 899,  2816, 5197, 13330, 7054, 2818,  3199,  811,   922,  350,  7514, 4452, 3449, 2663,  4708, 418,  1621, 1171, 3471, 88,    11345, 412,   1559,  194 };
    using mint = DynamicModint32<-1>;
    mint::set_mod(x);
    std::uint64_t h = x;
    h = ((h >> 16) ^ h) * 0x45d9f3b;
    h = ((h >> 16) ^ h) * 0x45d9f3b;
    h = ((h >> 16) ^ h) & 255;
    mint cur = bases[h];
    std::uint32_t d = x - 1;
    int s = std::countr_zero(d);
    d >>= s;
    cur = cur.pow(d);
    if (cur.val() == 1) return true;
    while (--s) {
        if (cur.val() == x - 1) return true;
        cur *= cur;
    }
    return cur.val() == x - 1;
}
template<bool trial_division = true> bool isPrime64(const std::uint64_t x) {
    if (x < 4294967296) return isPrime32<trial_division>(x);
    if constexpr (trial_division) {
        if (x % 2 == 0 || x % 3 == 0 || x % 5 == 0 || x % 7 == 0 || x % 11 == 0 || x % 13 == 0 || x % 17 == 0 || x % 19 == 0 || x % 23 == 0 || x % 29 == 0 || x % 31 == 0 || x % 37 == 0 || x % 41 == 0 || x % 43 == 0) return false;
    } else {
        if (x % 2 == 0) return false;
    }
    using mint = DynamicModint64<-1>;
    mint::set_mod(x);
    std::uint64_t d = x - 1;
    const int s = std::countr_zero(d);
    d >>= s;
    auto test = [&](std::uint64_t a) -> bool {
        mint cur = mint(a).pow(d);
        if (cur.val() <= 1) return true;
        int i = s;
        while (--i) {
            if (cur.val() == x - 1) return true;
            cur *= cur;
        }
        return cur.val() == x - 1;
    };
    return test(2) && test(325) && test(9375) && test(28178) && test(450775) && test(9780504) && test(1795265022);
}

int main() {
    int Q;
    fin >> Q;
    rep(Q) {
        ull N;
        fin >> N;
        fout << N << ' ' << isPrime64<false>(N) << '\n';
    }
}