#ifndef LOCAL #define FAST_IO #endif // ============ #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define OVERRIDE(a, b, c, d, ...) d #define REP2(i, n) for (i32 i = 0; i < (i32)(n); ++i) #define REP3(i, m, n) for (i32 i = (i32)(m); i < (i32)(n); ++i) #define REP(...) OVERRIDE(__VA_ARGS__, REP3, REP2)(__VA_ARGS__) #define PER(i, n) for (i32 i = (i32)(n) - 1; i >= 0; --i) #define ALL(x) begin(x), end(x) using namespace std; using u32 = unsigned int; using u64 = unsigned long long; using i32 = signed int; using i64 = signed long long; using f64 = double; using f80 = long double; template using Vec = vector; template bool chmin(T &x, const T &y) { if (x > y) { x = y; return true; } return false; } template bool chmax(T &x, const T &y) { if (x < y) { x = y; return true; } return false; } #ifdef INT128 using u128 = __uint128_t; using i128 = __int128_t; istream &operator>>(istream &is, i128 &x) { i64 v; is >> v; x = v; return is; } ostream &operator<<(ostream &os, i128 x) { os << (i64)x; return os; } istream &operator>>(istream &is, u128 &x) { u64 v; is >> v; x = v; return is; } ostream &operator<<(ostream &os, u128 x) { os << (u64)x; return os; } #endif [[maybe_unused]] constexpr i32 INF = 1000000100; [[maybe_unused]] constexpr i64 INF64 = 3000000000000000100; struct SetUpIO { SetUpIO() { #ifdef FAST_IO ios::sync_with_stdio(false); cin.tie(nullptr); #endif cout << fixed << setprecision(15); } } set_up_io; // ============ #ifdef DEBUGF #else #define DBG(x) (void) 0 #endif // ============ // ============ #include #include #include namespace poly { using Mint = atcoder::modint998244353; using Poly = std::vector; Poly add(Poly f, Poly g) { if (f.size() < g.size()) { std::swap(f, g); } for (int i = 0; i < (int)g.size(); ++i) { f[i] += g[i]; } return f; } Poly sub(Poly f, Poly g) { if (f.size() < g.size()) { std::swap(f, g); } for (int i = 0; i < (int)g.size(); ++i) { f[i] -= g[i]; } return f; } Poly mul(const Poly &f, const Poly &g) { return atcoder::convolution(f, g); } void dft(Poly &f) { atcoder::internal::butterfly(f); } void idft(Poly &f) { atcoder::internal::butterfly_inv(f); Mint inv = Mint::raw(f.size()).inv(); for (Mint &cf : f) { cf *= inv; } } } // namespace poly // ============ namespace poly { std::vector geometric_multipoint_evaluation(const Poly &f, int m, Mint a, Mint r) { int n = (int)f.size(); if (n == 0) { return std::vector(m, Mint()); } if (m == 0) { return std::vector(); } if (r == Mint()) { Mint ev; Mint p(1); for (int i = 0; i < n; ++i) { ev += f[i] * p; p *= a; } std::vector ret(m, f[0]); ret[0] = ev; return ret; } std::vector w(n + m - 1), w_inv(std::max(n, m)); { Mint v(1), pw(1); for (int i = 0; i < n + m - 1; ++i) { w[i] = v; v *= pw; pw *= r; } } { Mint inv = r.inv(); Mint v(1), pw(1); for (int i = 0; i < std::max(n, m); ++i) { w_inv[i] = v; v *= pw; pw *= inv; } } std::vector y(n); { Mint pw(1); for (int i = 0; i < n; ++i) { y[i] = f[i] * pw * w_inv[i]; pw *= a; } } std::reverse(y.begin(), y.end()); std::vector conv = mul(y, w); std::vector ans(conv.begin() + (n - 1), conv.begin() + (n + m - 1)); for (int i = 0; i < m; ++i) { ans[i] *= w_inv[i]; } return ans; } } // namespace poly // ============ using poly::Mint; constexpr u32 P = 998244353; constexpr u32 D = 1 << 20; constexpr u32 E = P / D; Vec mod_e(Mint a, i32 n) { i32 m = n / E; poly::Poly g(m); REP(i, m) { g[i] = a.pow((i64)E * E * i * i); } Vec ans = poly::geometric_multipoint_evaluation(g, E, Mint::raw(1), a.pow(2 * E)); REP(i, E) { ans[i] *= a.pow((i64)i * i); } REP(i, m * E, n) { ans[i % E] += a.pow((i64)i * i); } return ans; } Mint part_1(Mint a, i32 l) { poly::Poly f(l); REP(i, l) { f[i] = a.pow((i64)D * D * i * i); } Vec gme = poly::geometric_multipoint_evaluation(f, E, Mint::raw(1), a.pow(2 * D)); Vec moe = mod_e(a, D); Mint ans; REP(i, E) { ans += gme[i] * moe[i]; } return ans; } Mint part_2(Mint a, i32 l, i32 r) { Vec moe = mod_e(a, r); Mint ans; REP(i, E) { ans += a.pow((i64)2 * l * D * i) * moe[i]; } ans *= a.pow((i64)l * l * D * D); return ans; } Mint solve(Mint a, i32 n) { return part_1(a, n / D) + part_2(a, n / D, n % D); } int main() { i32 t; cin >> t; while (t--) { i32 a, n; cin >> a >> n; cout << solve(Mint::raw(a), n).val() << '\n'; } }