//#ifdef NACHIA
//#define _GLIBCXX_DEBUG
//#else
//#define NDEBUG
//#endif
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using i64 = long long;
using u64 = unsigned long long;
#define rep(i,n) for(int i=0; i<int(n); i++)
const i64 INF = 1001001001001001001;
template<typename A> void chmin(A& l, const A& r){ if(r < l) l = r; }
template<typename A> void chmax(A& l, const A& r){ if(l < r) l = r; }
using namespace std;

#include <cassert>
#include <utility>

namespace nachia{

// ax + by = gcd(a,b)
// return ( x, - )
std::pair<long long, long long> ExtGcd(long long a, long long b){
    long long x = 1, y = 0;
    while(b){
        long long u = a / b;
        std::swap(a-=b*u, b);
        std::swap(x-=y*u, y);
    }
    return std::make_pair(x, a);
}

} // namespace nachia

namespace nachia{

template<unsigned int MOD>
struct StaticModint{
private:
    using u64 = unsigned long long;
    unsigned int x;
public:

    using my_type = StaticModint;
    template< class Elem >
    static Elem safe_mod(Elem x){
        if(x < 0){
            if(0 <= x+MOD) return x + MOD;
            return MOD - ((-(x+MOD)-1) % MOD + 1);
        }
        return x % MOD;
    }

    StaticModint() : x(0){}
    StaticModint(const my_type& a) : x(a.x){}
    StaticModint& operator=(const my_type&) = default;
    template< class Elem >
    StaticModint(Elem v) : x(safe_mod(v)){}
    unsigned int operator*() const noexcept { return x; }
    my_type& operator+=(const my_type& r) noexcept { auto t = x + r.x; if(t >= MOD) t -= MOD; x = t; return *this; }
    my_type operator+(const my_type& r) const noexcept { my_type res = *this; return res += r; }
    my_type& operator-=(const my_type& r) noexcept { auto t = x + MOD - r.x; if(t >= MOD) t -= MOD; x = t; return *this; }
    my_type operator-(const my_type& r) const noexcept { my_type res = *this; return res -= r; }
    my_type operator-() const noexcept { my_type res = *this; res.x = ((res.x == 0) ? 0 : (MOD - res.x)); return res; }
    my_type& operator*=(const my_type& r)noexcept { x = (u64)x * r.x % MOD; return *this; }
    my_type operator*(const my_type& r) const noexcept { my_type res = *this; return res *= r; }
    my_type pow(unsigned long long i) const noexcept {
        my_type a = *this, res = 1;
        while(i){ if(i & 1){ res *= a; } a *= a; i >>= 1; }
        return res;
    }
    my_type inv() const { return my_type(ExtGcd(x, MOD).first); }
    unsigned int val() const noexcept { return x; }
    static constexpr unsigned int mod() { return MOD; }
    static my_type raw(unsigned int val) noexcept { auto res = my_type(); res.x = val; return res; }
    my_type& operator/=(const my_type& r){ return operator*=(r.inv()); }
    my_type operator/(const my_type& r) const { return operator*(r.inv()); }
};

} // namespace nachia

namespace nachia{

template<unsigned int MOD>
struct PrimitiveRoot{
    using u64 = unsigned long long;
    static constexpr u64 powm(u64 a, u64 i) {
        u64 res = 1, aa = a;
        for( ; i; i /= 2){
            if(i & 1) res = res * aa % MOD;
            aa = aa * aa % MOD;
        }
        return res;
    }
    static constexpr bool ExamineVal(unsigned int g){
        u64 t = MOD - 1;
        for(u64 d=2; d*d<=t; d+=1+(d&1)) if(t % d == 0){
            if(powm(g, (MOD - 1) / d) == 1) return false;
            while(t % d == 0) t /= d;
        }
        if(t != 1) if(powm(g, (MOD - 1) / t) == 1) return false;
        return true;
    }
    static constexpr unsigned int GetVal(){
        for(u64 x=2; x<MOD; x++) if(ExamineVal(x)) return x;
        return 0;
    }
    static const unsigned int val = GetVal();
};

} // namespace nachia

namespace nachia {

template<class mint>
struct NttInterface{

template<class Iter>
void Butterfly(Iter, int) const {}

template<class Iter>
void IButterfly(Iter, int) const {}

template<class Iter>
void BitReversal(Iter a, int N) const {
    for(int i=0, j=0; j<N; j++){
        if(i < j) std::swap(a[i], a[j]);
        for(int k = N>>1; k > (i^=k); k>>=1);
    }
}

};

} // namespace nachia

namespace nachia{

int Popcount(unsigned long long c) noexcept {
#ifdef __GNUC__
    return __builtin_popcountll(c);
#else
    c = (c & (~0ull/3)) + ((c >> 1) & (~0ull/3));
    c = (c & (~0ull/5)) + ((c >> 2) & (~0ull/5));
    c = (c & (~0ull/17)) + ((c >> 4) & (~0ull/17));
    c = (c * (~0ull/257)) >> 56;
    return c;
#endif
}

// please ensure x != 0
int MsbIndex(unsigned long long x) noexcept {
#ifdef __GNUC__
    return 63 - __builtin_clzll(x);
#else
    using u64 = unsigned long long;
    int q = (x >> 32) ? 32 : 0;
    auto m = x >> q;
    constexpr u64 hi = 0x88888888;
    constexpr u64 mi = 0x11111111;
    m = (((m | ~(hi - (m & ~hi))) & hi) * mi) >> 35;
    m = (((m | ~(hi - (m & ~hi))) & hi) * mi) >> 31;
    q += (m & 0xf) << 2;
    q += 0x3333333322221100 >> (((x >> q) & 0xf) << 2) & 0xf;
    return q;
#endif
}

// please ensure x != 0
int LsbIndex(unsigned long long x) noexcept {
#ifdef __GNUC__
    return __builtin_ctzll(x);
#else
    return MsbIndex(x & -x);
#endif
}

}

#include <iterator>
#include <array>

namespace nachia{

template <class mint>
struct NttFromAcl : NttInterface<mint> {

using u32 = unsigned int;
using u64 = unsigned long long;
    
static int ceil_pow2(int n) {
    int x = 0;
    while ((1U << x) < (u32)(n)) x++;
    return x;
}
    
static constexpr int bsf_constexpr(unsigned int n) {
    int x = 0;
    while (!(n & (1 << x))) x++;
    return x;
}

struct fft_info {
    static constexpr u32 g = nachia::PrimitiveRoot<mint::mod()>::val;
    static constexpr int rank2 = bsf_constexpr(mint::mod()-1);
    using RootTable = std::array<mint, rank2+1>;
    RootTable root, iroot, rate3, irate3;

    fft_info(){
        root[rank2] = mint(g).pow((mint::mod() - 1) >> rank2);
        iroot[rank2] = root[rank2].inv();
        for(int i=rank2-1; i>=0; i--){
            root[i] = root[i+1] * root[i+1];
            iroot[i] = iroot[i+1] * iroot[i+1];
        }
        mint prod = 1, iprod = 1;
        for(int i=0; i<=rank2-3; i++){
            rate3[i] = root[i+3] * prod;
            irate3[i] = iroot[i+3] * iprod;
            prod *= iroot[i+3];
            iprod *= root[i+3];
        }
    }
};

template<class RandomAccessIterator>
void Butterfly(RandomAccessIterator a, int n) const {
    int h = ceil_pow2(n);

    static const fft_info info;

    int len = 0;
    if((h-len)%2 == 1){
        int p = 1 << (h-len-1);
        for(int i=0; i<p; i++){
            mint l = a[i], r = a[i+p];
            a[i] = l+r; a[i+p] = l-r;
        }
        len++;
    }
    for( ; len < h; len += 2){
        int p = 1 << (h-len-2);
        mint rot = 1, imag = info.root[2];
        u64 mod2 = u64(mint::mod()) * mint::mod();
        for(int s=0; s<(1<<len); s++){
            if(s) rot *= info.rate3[LsbIndex(~(u32)(s-1))];
            mint rot2 = rot * rot;
            mint rot3 = rot2 * rot;
            int offset = (s << (h-len)) + p;
            for(int i=offset-p; i<offset; i++){
                u64 a0 = u64(a[i].val());
                u64 a1 = u64(a[i+p].val()) * rot.val();
                u64 a2 = u64(a[i+2*p].val()) * rot2.val();
                u64 a3 = u64(a[i+3*p].val()) * rot3.val();
                u64 a1na3imag = u64(mint(a1 + mod2 - a3).val()) * imag.val();
                u64 na2 = mod2 - a2;
                a[i] = a0 + a2 + a1 + a3;
                a[i+1*p] = a0 + a2 + (2 * mod2 - (a1 + a3));
                a[i+2*p] = a0 + na2 + a1na3imag;
                a[i+3*p] = a0 + na2 + (mod2 - a1na3imag);
            }
        }
    }
}

template<class RandomAccessIterator>
void IButterfly(RandomAccessIterator a, int n) const {
    int h = ceil_pow2(n);

    static const fft_info info;
    constexpr int MOD = mint::mod();

    int len = h;
    for( ; 1 < len; len -= 2){
        int p = 1 << (h-len);
        mint irot = 1, iimag = info.iroot[2];
        for(int s=0; s<(1<<(len-2)); s++){
            if(s) irot *= info.irate3[LsbIndex(~(u32)(s-1))];
            mint irot2 = irot * irot;
            mint irot3 = irot2 * irot;
            int offset = (s << (h-len+2)) + p;
            for(int i=offset-p; i<offset; i++){
                u64 a0 = a[i].val();
                u64 a1 = a[i+p].val();
                u64 a2 = a[i+2*p].val();
                u64 a3 = a[i+3*p].val();
                u64 a2na3iimag = mint((a2 + MOD - a3) * iimag.val()).val();
                a[i] = a0 + a1 + a2 + a3;
                a[i+p] = (a0 + (MOD - a1) + a2na3iimag) * irot.val();
                a[i+2*p] = (a0 + a1 + (MOD - a2) + (MOD - a3)) * irot2.val();
                a[i+3*p] = (a0 + (MOD - a1) + (MOD - a2na3iimag)) * irot3.val();
            }
        }
    }
    if(len == 1){
        int p = 1 << (h-len);
        for(int i=0; i<p; i++){
            mint l = a[i], r = a[i+p];
            a[i] = l+r; a[i+p] = l-r;
        }
    }
}

};

} // namespace nachia

namespace nachia {

struct BigintDecMulManager {
    using Int = int;
    using Arr = std::vector<Int>;
    using u32 = unsigned int;
    using i64 = long long;
    static const Int B = 1000000000;
    static const u32 MOD0 = 0x1c000001;
    static const u32 MOD1 = 0x6c000001;
    static const u32 MOD2 = 0x78000001;
    static const u32 I0_M1 = 1540148431;
    static const u32 I01_M2 = 1050399624;
    static const u32 I1_M2 = 10;
    static const u32 IB_M1 = 1575545083;
    static const u32 IB_M2 = 65929464;

    template<u32 MOD>
    static std::vector<u32> convMod(int z, int n, const Arr& a, const Arr& b){
        using Mint = StaticModint<MOD>;
        static auto ntt = NttFromAcl<Mint>();
        std::vector<Mint> a2(z);
        for(int i=0; i<(int)a.size(); i++) a2[i] = a[i];
        std::vector<Mint> b2(z);
        for(int i=0; i<(int)b.size(); i++) b2[i] = b[i];
        Mint c = Mint(z).inv();
        ntt.Butterfly(a2.begin(), z);
        ntt.Butterfly(b2.begin(), z);
        for(int i=0; i<z; i++) a2[i] *= b2[i] * c;
        ntt.IButterfly(a2.begin(), z);
        std::vector<u32> res(n);
        for(int i=0; i<n; i++) res[i] = a2[i].val();
        return res;
    }
    template<u32 M>
    static inline StaticModint<M> SubMod(u32 a, u32 b){
        return StaticModint<M>::raw(a<b ? a+M-b : a-b);
    }

    static Arr BigintDecMul(const Arr& a, const Arr& b){
        int n = a.size() + b.size();
        int n2 = 1; while(n2 < n) n2 *= 2;
        auto c0 = convMod<MOD0>(n2, n-1, a, b);
        auto c1 = convMod<MOD1>(n2, n-1, a, b);
        auto c2 = convMod<MOD2>(n2, n-1, a, b);
        std::vector<i64> c(n+1);
        using MintB = StaticModint<B>;
        using Mint1 = StaticModint<MOD1>;
        using Mint2 = StaticModint<MOD2>;
        auto i0m1 = Mint1::raw(I0_M1);
        auto i01m2 = Mint2::raw(I01_M2);
        auto ibm1 = Mint1::raw(IB_M1);
        auto ibm2 = Mint2::raw(IB_M2);
        auto i1m2 = Mint2::raw(I1_M2);
        auto m01_b = MintB::raw(MOD0) * MintB(MOD1);
        for(int i=0; i<n-1; i++){
            u32 d0to1 = (i0m1 * SubMod<MOD1>(c1[i], c0[i])).val();
            Mint2 x01m2 = Mint2::raw(c0[i]) + Mint2::raw(MOD0) * Mint2::raw(d0to1);
            MintB x01mB = MintB::raw(c0[i]) + MintB::raw(MOD0) * MintB(d0to1);
            MintB xmB = x01mB + m01_b * MintB((i01m2 * SubMod<MOD2>(c2[i], x01m2.val())).val());
            c[i] += xmB.val();
            Mint1 y1 = SubMod<MOD1>(c1[i], xmB.val()) * ibm1;
            Mint2 y2 = SubMod<MOD2>(c2[i], xmB.val()) * ibm2;
            i64 y12 = (i64)y1.val() + (i64)MOD1 * (i64)(i1m2 * SubMod<MOD2>(y2.val(), y1.val())).val();
            c[i+1] += y12 % B; c[i+2] += y12 / B;
        }
        Arr res(n);
        for(int i=0; i<n; i++){
            res[i] = c[i]%B;
            c[i+1] += c[i]/B;
        }
        if(res.back() == 0) res.pop_back();
        return res;
    }

};

};


namespace nachia {

struct BigintDec{
    using Int = int;
    using Arr = std::vector<Int>;

    BigintDec() : sign(0), A(0) {}
    BigintDec(int z){
        if(z == 0){ sign = 0; }
        else if(z < 0){ sign = -1; A = Arr(1, -z); }
        else{ sign = 1; A = Arr(1, z); }
    }
    BigintDec(const std::string& s) : sign(1) {
        auto it = s.begin();
        if(it != s.end()){
            if(*it == '-'){ sign = -1; it++; }
            else if(*it == '+'){ it++; }
        }
        while(it != s.end() && *it == '0') it++;
        if(it == s.end()){ sign = 0; }
        else {
            auto f = (s.end() - it);
            int e = int((f-1) / 9);
            int d = int((f-1) % 9);
            A.assign(e + 1, 0);
            for( ; it!=s.end(); it++){
                assert('0' <= *it && *it <= '9');
                A[e] = A[e] * 10 + (*it - '0');
                d--; if(d < 0){ d = 8; e -= 1; }
            }
        }
    }

    BigintDec operator+(const BigintDec& r) const {
        if(r.isZero()) return *this;
        if(isZero()) return r;
        auto x = (sign == r.sign) ?
            uintSum(*this, r) : uintDiff(*this, r);
        x.sign *= sign;
        return x;
    }

    BigintDec operator-() const { return raw(-sign, A); }

    BigintDec operator-(const BigintDec& r) const {
        if(r.isZero()) return *this;
        if(isZero()) return -r;
        auto x = (sign == r.sign) ?
            uintDiff(*this, r) : uintSum(*this, r);
        x.sign *= sign;
        return x;
    }

    BigintDec operator*(const BigintDec& r) const {
        if(isZero() || r.isZero()) return Zero();
        return raw(sign * r.sign, uintMul(*this, r));
    }

    std::pair<BigintDec, BigintDec> divrem(const BigintDec& r) const {
        assert(!r.isZero());
        if(isZero() || CmpAbs(*this, r) == 1) return { Zero(), *this };
        auto invr = r.invFlex(len()+1);
        auto a2 = (*this * invr).shiftRight(len() + r.len() + 2);
        a2.sign = sign * r.sign;
        auto rem = (*this) - (r * a2);
        if(CmpAbs(r, rem) >= 0){
            rem = rem - r;
            a2 = a2 + BigintDec("1");
        }
        return std::make_pair(std::move(a2), std::move(rem));
    }

    BigintDec operator/(const BigintDec& r){
        assert(!r.isZero());
        return divrem(r).first;
    }

    BigintDec& operator*=(int x){
        if(x == 0) return (*this) = Zero();
        i64 y = std::abs(x);
        i64 c = 0;
        for(int i=0; i<len(); i++){
            c += A[i] * y;
            A[i] = c % B; c /= B;
        }
        if(c >= B){ A.push_back(c % B); c /= B; }
        if(c) A.push_back(c);
        if(x < 0) sign = -sign;
        return *this;
    }

    static BigintDec Zero(){ return BigintDec(); }
    bool isZero() const { return sign == 0; }
    std::string toString() const {
        if(isZero()) return "0";
        std::string s;
        for(int i=0; i<len()-1; i++){
            int a = A[i];
            for(int d=0; d<9; d++){ s.push_back('0'+a%10); a /= 10; }
        }
        for(Int a=A[len()-1]; a!=0; a/=10) s.push_back('0'+a%10);
        if(sign < 0) s.push_back('-');
        std::reverse(s.begin(), s.end());
        return s;
    }
    bool operator<(const BigintDec& r) const {
        if(sign != r.sign) return sign < r.sign;
        return CmpAbs(*this, r) == sign;
    }
    bool operator>(const BigintDec& r) const { return r < *this; }
    bool operator<=(const BigintDec& r) const { return !(r < *this); }
    bool operator>=(const BigintDec& r) const { return !(*this < r); }
    bool operator==(const BigintDec& r) const { return sign == r.sign && A == r.A; }
    bool operator!=(const BigintDec& r) const { return !(*this == r); }
private:
    using Self = BigintDec;
    using i64 = long long;
    int sign;
    std::vector<Int> A;
    static const int B = 1000000000;
    int len() const { return int(A.size()); }
    Int dig(int z) const { return z < len() ? A[z] : 0; }
    Int& operator[](int z){ return A[z]; }
    const Int& operator[](int z) const { return A[z]; }
    static int CmpUintPos(const Self& l, const Self& r){
        if(l.len() != r.len()) return std::max(l.len(), r.len()) - 1;
        for(int i=l.len()-1; i>=0; i--) if(l[i] != r[i]) return i;
        return -1;
    }
    static int CmpAbs(const Self& l, const Self& r){
        int k = CmpUintPos(l, r);
        if(k < 0) return 0;
        return l.dig(k) < r.dig(k) ? 1 : -1;
    }
    static Self raw(int sign, Arr a){
        if(a.empty()) sign = 0;
        while(!a.empty() && a.back() == 0) a.pop_back();
        Self res; res.sign = sign; res.A = std::move(a);
        return res;
    }
    static Self uintDiff2(const Self& l, const Self& r, int k){
        Arr A(k + 1);
        for(int i=0; i<=k; i++) A[i] = l[i];
        int j = std::min(k+1, r.len());
        Int v = 0;
        for(int i=0; i<j; i++){
            v = v + A[i] - r[i];
            if(v < 0){ A[i] = v + B; v = -1; }
            else { A[i] = v; v = 0; }
        }
        for(int i=j; v!=0; i++){
            v = v + A[i];
            if(v < 0){ A[i] = v + B; v = -1; }
            else { A[i] = v; v = 0; }
        }
        return raw(1, std::move(A));
    }
    static Self uintDiff(const Self& l, const Self& r){
        int k = CmpUintPos(l, r);
        if(k == -1) return Zero();
        if(l.dig(k) > r.dig(k)) return uintDiff2(l, r, k);
        auto x = uintDiff2(r, l, k); x.sign = -x.sign;
        return x;
    }
    static Self uintSum(const Self& l, const Self& r){
        if(l.len() > r.len()) return uintSum(r, l);
        Arr A(r.len() + 1);
        for(int i=0; i<l.len(); i++) A[i] = l[i];
        Int v = 0;
        for(int i=0; i<r.len(); i++){
            v = v + A[i] + r[i];
            if(B <= v){ A[i] = v - B; v = 1; }
            else { A[i] = v; v = 0; }
        }
        if(v != 0) A[r.len()] = v; else A.pop_back();
        return raw(1, std::move(A));
    }
    static Arr uintMul(const Self& l, const Self& r){
        if(l.len() >= 30 && r.len() >= 30){
            return BigintDecMulManager::BigintDecMul(l.A, r.A);
        }
        int z = l.len() + r.len();
        Arr a(z);
        for(int i=0; i<l.len(); i++) for(int j=0; j<r.len(); j++){
            i64 x = (i64)(l[i]) * r[j] + a[i+j];
            a[i+j] = x % B; a[i+j+1] += x / B;
        }
        if(a.back() == 0) a.pop_back();
        return a;
    }
    Self shiftLeft(int delta) const {
        if(isZero()) return Zero();
        Arr a(len() + delta);
        for(int i=0; i<len(); i++) a[i+delta] = A[i];
        return raw(sign, std::move(a));
    }
    Self shiftRight(int delta) const {
        if(len() <= delta) return Zero();
        Arr a(len() - delta);
        for(int i=delta; i<len(); i++) a[i-delta] = A[i];
        return raw(sign, std::move(a));
    }
    Self shiftToLength(int tg) const {
        return len() < tg ? shiftLeft(tg - len())
            : shiftRight(len() - tg);
    }
    void negate(){ sign = -sign; }
    Self invFlex(int prec) const {
        Int t = B / (A[len()-1] + 1);
        auto a2 = *this; a2 *= t;
        auto b2 = a2.invPrec(prec);
        b2 *= t;
        return b2;
    }
    Self invPrec(int prec){
        if(prec == 1){
            Int b = A[len()-1];
            Arr a(3); a[2] = 1; a[1] = i64(B) * B / b - B;
            return raw(sign, std::move(a));
        }
        int subp = (prec + 1) / 2;
        auto b = invPrec(subp);
        auto ab = (shiftToLength(prec+1) * b).shiftRight(subp+1);
        auto ab2 = Self("2").shiftLeft(prec+1) - ab;
        return (ab2 * b).shiftRight(subp + 1);
    }
};

}

namespace {

std::istream& operator>>(std::istream& i, nachia::BigintDec& d){
    std::string s; i >> s;
    d = nachia::BigintDec(s);
    return i;
}

std::ostream& operator<<(std::ostream& o, const nachia::BigintDec& d){
    return o << d.toString();
}

}




namespace nachia{

namespace prime_sieve_explicit_internal{
    std::vector<bool> isprime = { false }; // a[x] := isprime(2x+1)

    void CalcIsPrime(int z){
        if((int)isprime.size() *2+1 < z+1){
            int new_z = isprime.size();
            while(new_z*2+1 < z+1) new_z *= 2;
            z = new_z-1;
            isprime.resize(z+1, true);
            for(int i=1; i*(i+1)*2<=z; i++) if(isprime[i]){
                for(int j=i*(i+1)*2; j<=z; j+=i*2+1) isprime[j] = false;
            }
        }
    }
    
    std::vector<int> prime_list = {2};
    int prime_list_max = 0;

    void CalcPrimeList(int z){
        while((int)prime_list.size() < z){
            if((int)isprime.size() <= prime_list_max + 1) CalcIsPrime(prime_list_max * 2 + 10);
            for(int p=prime_list_max+1; p<(int)isprime.size(); p++){
                if(isprime[p]) prime_list.push_back(p*2+1);
            }
            prime_list_max = isprime.size() - 1;
        }
    }

    void CalcPrimeListUntil(int z){
        if(prime_list_max < z){
            CalcIsPrime(z);
            for(int p=prime_list_max+1; p<(int)isprime.size(); p++){
                if(isprime[p]) prime_list.push_back(p*2+1);
            }
            prime_list_max = isprime.size() - 1;
        }
    }

}


bool IsprimeExplicit(int n){
    using namespace prime_sieve_explicit_internal;
    if(n == 2) return true;
    if(n % 2 == 0) return false;
    CalcIsPrime(n);
    return isprime[(n-1)/2];
}

int NthPrimeExplicit(int n){
    using namespace prime_sieve_explicit_internal;
    CalcPrimeList(n);
    return prime_list[n];
}

int PrimeCountingExplicit(int n){
    using namespace prime_sieve_explicit_internal;
    if(n < 2) return 0;
    CalcPrimeListUntil(n);
    auto res = std::upper_bound(prime_list.begin(), prime_list.end(), n) - prime_list.begin();
    return (int)res;
}

// [l, r)
std::vector<bool> SegmentedSieveExplicit(long long l, long long r){
    assert(0 <= l); assert(l <= r);
    long long d = r - l;
    if(d == 0) return {};
    std::vector<bool> res(d, true);
    for(long long p=2; p*p<=r; p++) if(IsprimeExplicit(p)){
        long long il = (l+p-1)/p, ir = (r+p-1)/p;
        if(il <= p) il = p;
        for(long long i=il; i<ir; i++) res[i*p-l] = false;
    }
    if(l < 2) for(long long p=l; p<2 && p<r; p++) res[l-p] = false;
    return res;
}


} // namespace nachia

namespace nachia{

class DynamicModSupplier{
    using u64 = unsigned long long;
    using Int = unsigned int;
private:
    u64 imod;
    Int mod;
    // atcoder library
    u64 reduce2(u64 z) const noexcept {
        // atcoder library
#ifdef _MSC_VER
        u64 x; _umul128(z, im, &x);
#else
        using u128 = unsigned __int128;
        u64 x = (u64)(((u128)(z)*imod) >> 64);
#endif
        return z - x * mod;
    }
public:
    DynamicModSupplier(unsigned int MOD = 998244353) : mod(MOD) {
        assert(2 <= MOD);
        assert(MOD < (1u << 31));
        imod = (u64)(-1) / mod + 1;
    }
    Int reduce(u64 z) const noexcept {
        Int v = reduce2(z);
        if(mod <= v) v += mod;
        return v;
    }
    Int add(Int a, Int b) const { a += b; if(a >= mod){ a -= mod; } return a; }
    Int sub(Int a, Int b) const { a -= b; if(a >= mod){ a += mod; } return a; }
    Int mul(Int a, Int b) const { return reduce((u64)a * b); }
    Int muladd(Int a, Int b, Int c) const { return reduce((u64)a * b + c); }
    Int inv(Int a) const {
        Int v = ExtGcd(a, mod).first;
        return (v < mod) ? v : (v + mod);
    }
    Int pow(Int a, u64 i) const {
        Int r = a, ans = 1;
        while(i){
            if(i & 1) ans = mul(ans, r);
            i /= 2;
            r = mul(r, r);
        }
        return ans;
    }
    Int getMod() const { return mod; }
};

} // namespace nachia

namespace nachia{

template<unsigned int IDENTIFER, class IDENTIFER2 = void>
class DynamicModint{
    using Int = unsigned int;
    using MyType = DynamicModint;
private:
    static DynamicModSupplier _c;
    Int v;
    template< class Elem >
    static Elem SafeMod(Elem x, Int mod){
        if(x < 0){
            if(0 <= x+mod) return x + mod;
            return mod - ((-(x+mod)-1) % mod + 1);
        }
        return x % mod;
    }
public:
    DynamicModint() : v(0) {}
    DynamicModint(const MyType& r) : v(r.v) {}
    MyType& operator=(const MyType&) = default;
    DynamicModint(long long x){ v = SafeMod(x, _c.getMod()); }
    static MyType raw(Int _v){ MyType res; res.v = _v; return res; }
    static void setMod(DynamicModSupplier sup){ _c = std::move(sup); }
    MyType operator+=(MyType r){ return v = _c.add(v, r.v); }
    MyType operator+(MyType r) const { return raw(_c.add(v, r.v)); }
    MyType operator-=(MyType r){ return v = _c.sub(v, r.v); }
    MyType operator-(MyType r) const { return raw(_c.sub(v, r.v)); }
    MyType operator-() const { return raw(v ? _c.getMod()-v : 0); }
    MyType operator*=(MyType r){ return v = _c.mul(v, r.v); }
    MyType operator*(MyType r) const { return raw(_c.mul(v, r.v)); }
    MyType operator/=(MyType r){ return v = _c.mul(v, _c.inv(r.v)); }
    MyType operator/(MyType r) const { return raw(_c.mul(v, _c.inv(r.v))); }
    MyType inv() const { return raw(_c.inv(v)); }
    MyType pow(unsigned long long r) const { return raw(_c.pow(v, r)); }
    MyType mulAdd(MyType mul, MyType add) const { return raw(_c.muladd(v, mul.v, add.v)); }
    Int val() const { return v; }
    Int operator*() const { return v; }
    static Int mod(){ return _c.getMod(); }
};

template<unsigned int IDENTIFER, class IDENTIFER2>
DynamicModSupplier DynamicModint<IDENTIFER, IDENTIFER2>::_c;

} // namespace nachia

void testcase(){
    using Int = nachia::BigintDec;
    using Modint = nachia::DynamicModint<0>;
    i64 N; cin >> N;
    if(N == 1){
        cout << "1/1\n";
        return;
    }
    vector<i64> A;
    for(i64 p=2; p<=N; p++) if(nachia::IsprimeExplicit(p)){
        i64 q = p; while(q*p <= N) q *= p;
        A.push_back(q);
    }
    N = A.size();
    sort(A.begin(), A.end());
    vector<int> X(N,-1), Y(N,-1);
    rep(i,N-1){ X.push_back(i*2); Y.push_back(i*2+1); }
    int n = X.size();
    vector<Int> prod(n);
    rep(i,N) prod[i] = A[i];
    for(int i=N; i<n; i++) prod[i] = prod[X[i]] * prod[Y[i]];
    //for(auto a : prod) cout << a << endl;
    //cout << endl;
    vector<Int> Z(n);
    Z.back() = 1;
    for(int i=n-1; i>=N; i--){
        Z[X[i]] = (Z[i] * prod[Y[i]]).divrem(prod[X[i]]).second;
        Z[Y[i]] = (Z[i] * prod[X[i]]).divrem(prod[Y[i]]).second;
    }
    //rep(i,N) cout << A[i] << " ";
    //cout << endl;
    vector<int> Q(N);
    rep(i,N){
        Modint::setMod(A[i]);
        Q[i] = Modint(stoll(Z[i].toString())).inv().val();
    }
    //rep(i,N) cout << Q[i] << " ";
    //cout << endl;
    using M2 = nachia::StaticModint<998244353>;
    M2 f = 0;
    M2 g = 1;
    rep(i,N){
        auto a = M2(A[i]).inv();
        f += a * M2(Q[i]);
        g *= a;
    }
    int p = (f - g).val();
    //cout << p << endl;
    rep(i,N){
        if(i+p>=N){
            cout << (Q[i] - A[i]);
        } else {
            if(i) cout << "+";
            cout << Q[i];
        }
        cout << "/";
        cout << A[i];
    }

    cout << "\n";
}

int main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int N; cin >> N;
    rep(n,N) testcase();
    return 0;
}