結果
| 問題 | No.3030 ミラー・ラビン素数判定法のテスト |
| ユーザー |
 sortA0329
|
| 提出日時 | 2024-03-09 07:15:26 |
| 言語 | C++23 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
AC
|
| 実行時間 | 32 ms / 9,973 ms |
| コード長 | 46,846 bytes |
| コンパイル時間 | 5,975 ms |
| コンパイル使用メモリ | 442,188 KB |
| 実行使用メモリ | 6,820 KB |
| 最終ジャッジ日時 | 2024-09-29 21:10:48 |
| 合計ジャッジ時間 | 6,660 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge2 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 2 ms
6,816 KB |
| testcase_01 | AC | 2 ms
6,816 KB |
| testcase_02 | AC | 2 ms
6,816 KB |
| testcase_03 | AC | 1 ms
6,816 KB |
| testcase_04 | AC | 17 ms
6,820 KB |
| testcase_05 | AC | 18 ms
6,816 KB |
| testcase_06 | AC | 10 ms
6,816 KB |
| testcase_07 | AC | 9 ms
6,820 KB |
| testcase_08 | AC | 9 ms
6,816 KB |
| testcase_09 | AC | 32 ms
6,816 KB |
ソースコード
#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';
}
}