#if __INCLUDE_LEVEL__ == 0
#include __BASE_FILE__

void solve() {
    ll t;
    ll N, M, K;
    ll a = 0, b = 0, c = 0;
    string S, T;

    cin >>N;
    cout << (N&1) <<'\n';
}

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << std::fixed << std::setprecision(20);
    int t = 1;
        cin >> t;
    rep(_, t) solve();
}
#elif __INCLUDE_LEVEL__ == 2

#elif __INCLUDE_LEVEL__ == 1
#pragma once
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>

#include <atcoder/all>
using namespace std;
using namespace atcoder;
using ll = long long;
using ld = long double;
using Graph = vector<vector<int> >;
using vi = vector<int>;
using vl = vector<long>;
using vll = vector<long long>;
using vb = vector<bool>;
using vvi = vector<vi>;
using vvl = vector<vl>;
using vvb = vector<vb>;
using vvvb = vector<vvb>;
using vvll = vector<vll>;
using vvvll = vector<vvll>;
using vvvvll = vector<vvvll>;
using vvvvvll = vector<vvvvll>;
using vd = vector<double>;
using vvd = vector<vd>;
using vvvd = vector<vvd>;
using vld = vector<long double>;
using vvld = vector<vld>;
using vvvld = vector<vvld>;
using vc = vector<char>;
using vvc = vector<vc>;
using vs = vector<string>;
using pii = pair<long long, long long>;
using mint = modint1000000007;
#define reps(i, a, n) for (ll i = (a); i < (ll)(n); i++)
#define rep(i, n) for (ll i = (0); i < (ll)(n); i++)
#define rrep(i, n) for (ll i = (1); i < (ll)(n + 1); i++)
#define repd(i, n) for (ll i = n - 1; i >= 0; i--)
#define rrepd(i, n) for (ll i = n; i >= 1; i--)
#define ALL(n) n.begin(), n.end()
#define rALL(n) n.rbegin(), n.rend()
#define fore(i, a) for (auto& i : a)
#define IN(a, x, b) (a <= x && x < b)
#define IN(a, x, b) (a <= x && x < b)
#define INIT                          \
    std::ios::sync_with_stdio(false); \
    std::cin.tie(0);

#pragma once

template <typename T>
// [0,M)についての階上を求める
vector<T> KAI(int M) {
    vector<T> kai(M, 1);
    rep(i, M - 1) { kai[i + 1] = kai[i] * (i + 1); }
    return kai;
}
template <typename T>
vector<T> DIV(int M) {
    vector<T> kai = KAI<T>(M), div(M, 1);
    div.back() /= kai.back();
    for (int i = M - 2; i >= 0; --i) {
        div[i] = div[i + 1] * (i + 1);
    }
    return div;
}

long long Power(long long a, long long b, long long m) {
    long long p = a, Answer = 1;
    p %= m;
    for (int i = 0; i < 62; i++) {
        ll wari = (1LL << i);
        if ((b / wari) % 2 == 1) {
            Answer %= m;
            Answer = (Answer * p) % m;
            // 「a の 2^i 乗」が掛けられるとき
        }
        ll t = p % m;
        p = (t * t) % m;
        // cout << p << endl;
    }
    return Answer;
}

// a ÷ b を m で割った余りを返す関数え
long long Division(long long a, long long b, long long m) {
    return (a * Power(b, m - 2, m)) % m;
}
template <class T>
void output(T& W, bool x) {
    cout << W;
    if (!x)
        cout << ' ';
    else
        cout << endl;
    return;
}
// sは改行するか否かを表す
template <class T>
void output(vector<T>& W, bool s) {
    rep(i, W.size()) { output(W[i], ((i == W.size() - 1) || s)); }
    return;
}
// sは改行するか否かを表す
template <class T>
void output(vector<vector<T> >& W, bool s) {
    rep(i, W.size()) { output(W[i], s); }
    return;
}
template <class T>
T vectorsum(vector<T>& W, int a, int b) {
    return accumulate(W.begin() + a, W.end() + b, (T)0);
}
template <class T>
T vectorsum(vector<T>& W) {
    int b = W.size();
    return accumulate(ALL(W), (T)0);
}
template <class T>
inline T CHMAX(T& a, const T b) {
    return a = (a < b) ? b : a;
}
template <class T>
inline T CHMIN(T& a, const T b) {
    return a = (a > b) ? b : a;
}
template <class T>
void input(T& W) {
    cin >> W;
    return;
}

template <class T>
void input(vector<T>& W) {
    for (auto& u : W) input(u);
    return;
}
template <class T, class TT>
void add(T& W, TT& a) {
    W += a;
    return;
}
template <class T>
void add(vector<T>& W, vector<T>& a) {
    rep(i, W.size()) add(W[i], a[i]);
}
template <class T>
void add(T& W, T& a) {
    W += a;
}
template <class T, class TT>
void add(vector<T>& W, TT a) {
    for (auto& u : W) add(u, a);
    return;
}

vll dx = {1, -1, 0, 0}, dy = {0, 0, 1, -1};

void Yes(bool b) {
    if (b)
        cout << "Yes" << '\n';
    else
        cout << "No" << '\n';
}
struct TRI {
    ll a;
    ll b;
    ll c;
    ll d;
};
bool operator>(const TRI& r, const TRI& l) {
    return (r.a > l.a | (r.a == l.a & r.b > l.b) |
            (r.a == l.a & r.b == l.b & r.c > l.c));
}
bool operator<(const TRI& r, const TRI& l) {
    return (r.a < l.a | (r.a == l.a & r.b < l.b) |
            (r.a == l.a & r.b == l.b & r.c < l.c));
}
struct TRK {
    ll a;
    ll b;
    ll c;
};
bool operator>(const TRK& r, const TRK& l) {
    return (r.a > l.a | (r.a == l.a & r.b > l.b) |
            (r.a == l.a & r.b == l.b & r.c > l.c));
}
bool operator<(const TRK& r, const TRK& l) {
    return (r.a < l.a | (r.a == l.a & r.b < l.b) |
            (r.a == l.a & r.b == l.b & r.c < l.c));
}
struct Mo {
    int n;
    vector<pair<int, int> > lr;

    explicit Mo(int n) : n(n) {}

    void add(int l, int r) { /* [l, r) */ lr.emplace_back(l, r); }

    template <typename AL, typename AR, typename EL, typename ER, typename O>
    void build(const AL& add_left, const AR& add_right, const EL& erase_left,
               const ER& erase_right, const O& out) {
        int q = (int)lr.size();
        int bs = n / min<int>(n, sqrt(q));
        vector<int> ord(q);
        iota(begin(ord), end(ord), 0);
        sort(begin(ord), end(ord), [&](int a, int b) {
            int ablock = lr[a].first / bs, bblock = lr[b].first / bs;
            if (ablock != bblock) return ablock < bblock;
            return (ablock & 1) ? lr[a].second > lr[b].second
                                : lr[a].second < lr[b].second;
        });
        int l = 0, r = 0;
        for (auto idx : ord) {
            while (l > lr[idx].first) add_left(--l, r);
            while (r < lr[idx].second) add_right(l, r++);
            while (l < lr[idx].first) erase_left(l++, r);
            while (r > lr[idx].second) erase_right(l, --r);
            out(idx);
        }
    }

    template <typename A, typename E, typename O>
    void build(const A& add, const E& erase, const O& out) {
        build(add, add, erase, erase, out);
    }
};

namespace RangeChMinMaxAddSum {
template <typename Num>
inline Num second_lowest(Num a, Num a2, Num c, Num c2) noexcept {
    // a < a2, c < c2 のとき全引数を昇順ソートして二番目の値
    return a == c    ? std::min(a2, c2)
           : a2 <= c ? a2
           : c2 <= a ? c2
                     : std::max(a, c);
}
template <typename Num>
inline Num second_highest(Num a, Num a2, Num b, Num b2) noexcept {
    // a > a2, b > b2 のとき全引数を降順ソートして二番目の値
    return a == b    ? std::max(a2, b2)
           : a2 >= b ? a2
           : b2 >= a ? b2
                     : std::min(a, b);
}

using BNum = long long;
constexpr BNum BINF = 1LL << 61;

struct S {
    BNum lo, hi, lo2, hi2,
        sum;  // 区間最小・最大値，区間最小・最大から二番目の値，区間総和
    unsigned sz, nlo, nhi;  // 区間要素数，区間最小・最大値をとる要素の個数
    bool fail;
    S()
        : lo(BINF),
          hi(-BINF),
          lo2(BINF),
          hi2(-BINF),
          sum(0),
          sz(0),
          nlo(0),
          nhi(0),
          fail(0) {}
    S(BNum x, unsigned sz_ = 1)
        : lo(x),
          hi(x),
          lo2(BINF),
          hi2(-BINF),
          sum(x * sz_),
          sz(sz_),
          nlo(sz_),
          nhi(sz_),
          fail(0) {}
};

S e() { return S(); }

S op(S l, S r) {
    S ret;
    ret.lo = std::min(l.lo, r.lo), ret.hi = std::max(l.hi, r.hi);
    ret.lo2 = second_lowest(l.lo, l.lo2, r.lo, r.lo2);
    ret.hi2 = second_highest(l.hi, l.hi2, r.hi, r.hi2);
    ret.sum = l.sum + r.sum, ret.sz = l.sz + r.sz;
    ret.nlo = l.nlo * (l.lo <= r.lo) + r.nlo * (r.lo <= l.lo);
    ret.nhi = l.nhi * (l.hi >= r.hi) + r.nhi * (r.hi >= l.hi);
    return ret;
}

struct F {
    BNum lb, ub, bias;
    F(BNum chmax_ = -BINF, BNum chmin_ = BINF, BNum add = 0)
        : lb(chmax_), ub(chmin_), bias(add) {}
    static F chmin(BNum x) noexcept { return F(-BINF, x, BNum(0)); }
    static F chmax(BNum x) noexcept { return F(x, BINF, BNum(0)); }
    static F add(BNum x) noexcept { return F(-BINF, BINF, x); };
};

F composition(F fnew, F fold) {
    F ret;
    ret.lb =
        std::max(std::min(fold.lb + fold.bias, fnew.ub), fnew.lb) - fold.bias;
    ret.ub =
        std::min(std::max(fold.ub + fold.bias, fnew.lb), fnew.ub) - fold.bias;
    ret.bias = fold.bias + fnew.bias;
    return ret;
}

F id() { return F(); }

S mapping(F f, S x) {
    if (x.sz == 0)
        return e();
    else if (x.lo == x.hi or f.lb == f.ub or f.lb >= x.hi or f.ub <= x.lo) {
        return S(std::min(std::max(x.lo, f.lb), f.ub) + f.bias, x.sz);
    } else if (x.lo2 == x.hi) {
        x.lo = x.hi2 = std::max(x.lo, f.lb) + f.bias;
        x.hi = x.lo2 = std::min(x.hi, f.ub) + f.bias;
        x.sum = x.lo * x.nlo + x.hi * x.nhi;
        return x;
    } else if (f.lb < x.lo2 and f.ub > x.hi2) {
        BNum nxt_lo = std::max(x.lo, f.lb), nxt_hi = std::min(x.hi, f.ub);
        x.sum +=
            (nxt_lo - x.lo) * x.nlo - (x.hi - nxt_hi) * x.nhi + f.bias * x.sz;
        x.lo = nxt_lo + f.bias, x.hi = nxt_hi + f.bias, x.lo2 += f.bias,
        x.hi2 += f.bias;
        return x;
    }
    x.fail = 1;
    return x;
}
using segtree = atcoder::lazy_segtree<S, op, e, F, mapping, composition, id>;
}  // namespace RangeChMinMaxAddSum

std::random_device rnd;
std::mt19937 mt(rnd());
default_random_engine engineX(rnd());

// 平均0.0、標準偏差1.0で分布させる
std::normal_distribution<> seikidist(0.0, 1.0);
template <class T>
// 0以上K未満の整数を等確率で発生させる
long long randomX(T K) {
    uniform_int_distribution<ll> select(0, K - 1);
    return select(mt);
}
template <typename T>
vector<T> dycstra(vector<vector<pair<ll, T> > > G, ll N, ll K) {
    vb kaku(N, false);
    vector<T> cur(N, 1e18);
    cur[K] = 0;
    priority_queue<pair<T, ll>, vector<pair<T, ll> >, greater<pair<T, ll> > > Q;
    Q.push(make_pair(cur[K], K));
    while (!Q.empty()) {
        ll pos = Q.top().second;
        Q.pop();
        if (kaku[pos]) continue;
        kaku[pos] = true;
        for (ll i = 0; i < G[pos].size(); i++) {
            ll nex = G[pos][i].first;
            T cost = G[pos][i].second;
            if (cur[nex] > cur[pos] + cost) {
                cur[nex] = cur[pos] + cost;
                Q.push(make_pair(cur[nex], nex));
            }
        }
    }
    return cur;
}
// 意図的な衝突を防ぐためのカスタムハッシャー
struct SafeHasher {
    static uint64_t splitmix64(uint64_t x) {
        // 固定値ではなく、ビットを十分に拡散させるためのミキシング関数
        // http://xorshift.di.unimi.it/splitmix64.c
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        // static修飾子により、プログラム実行中に一度だけ初期化される
        static const uint64_t FIXED_RANDOM = []() {
            std::random_device rd;
            // 64ビットの高品質な乱数生成器
            std::mt19937_64 gen(rd());
            std::uniform_int_distribution<uint64_t> dis;
            return dis(gen);
        }();
        return splitmix64(x + FIXED_RANDOM);
    }
};

namespace rolling_hash_on_segtree_INVAl {
struct Sx {
    ll value;  // 値
    ll x;  // 乱択で選ばれた数をHASHとすると右側にいくつHASYがあるか(説明が難しい)
    ll mod;  // modはmod
             // 値更新型の遅延セグ木を作りたければ長さを追加する必要もある
};
Sx op(Sx a, Sx b) {
    return {((a.value * b.x) % a.mod + b.value) % a.mod, (a.x * b.x) % a.mod,
            a.mod};
}
// １つ目のmodに対応した単位元
Sx e() { return {0, 1, 998244353}; }

// 2つ目のmodに対応した単位元
Sx e2() { return {0, 1, 1000000007}; }
// 念のため２つ用意してある(1つで十分だと思う...)
vector<ll> MOD = {998244353, 1000000007};
segtree<Sx, op, e> segS, segT;
segtree<Sx, op, e2> segS1, segT1;

ll a = randomX(998244351) + 2;
ll b = randomX(1000000005) + 2;

vector<ll> HASH = {a, b};

// 参考(https://nyaannyaan.github.io/library/string/rolling-hash-on-segment-tree.hpp.html)
struct rolling_hash_on_segtree {
   private:
    int n{};
    vector<ll> A, B;

   public:
    rolling_hash_on_segtree() = default;
    explicit rolling_hash_on_segtree(int n, vector<ll> A, vector<ll> B)
        : n(n), A(A), B(B) {
        build(n, A, B);
    };
    explicit rolling_hash_on_segtree(vector<ll> A, vector<ll> B)
        : rolling_hash_on_segtree(A.size(), A, B) {};
    void build(int n, vector<ll>& A, vector<ll>& B) {
        segtree<Sx, op, e> r(n);
        segS = r;
        segT = r;
        rep(i, A.size()) segS.set(i, {A[i], a, MOD[0]});
        rep(i, B.size()) segT.set(i, {B[i], a, MOD[0]});
        segtree<Sx, op, e2> r2(n);
        segS1 = r2;
        segT1 = r2;
        rep(i, A.size()) segS1.set(i, {A[i], b, MOD[1]});
        rep(i, B.size()) segT1.set(i, {B[i], b, MOD[1]});
        return;
    }
    // １番目のk番目の要素をkに変更する
    void setS(int k, ll x) {
        segS.set(k, {x, HASH[0], MOD[0]}), segS1.set(k, {x, HASH[1], MOD[1]});
    }
    // 2番目のk番目の要素をkに変更する
    void setT(int k, ll x) {
        segT.set(k, {x, HASH[0], MOD[0]}), segT1.set(k, {x, HASH[1], MOD[1]});
    }

    // i∈[l,r)を満たす１番目の文字列のハッシュ値
    vector<ll> prodS(int l, int r) {
        return {segS.prod(l, r).value, segS1.prod(l, r).value};
    }
    // i∈[l,r)を満たす2番目の文字列のハッシュ値
    vector<ll> prodT(int l, int r) {
        return {segT.prod(l, r).value, segT1.prod(l, r).value};
    }
    // i∈[0,n)を満たす１番目の文字列のハッシュ値
    vector<ll> all_prodS() {
        return {segS.all_prod().value, segS1.all_prod().value};
    }
    // i∈[0,n)を満たす2番目の文字列のハッシュ値
    vector<ll> all_prodT() {
        return {segT.all_prod().value, segT1.all_prod().value};
    }
    // 1番目の文字列[l,r)と2番目の文字列[l1,r1)の文字列の一致判定
    bool same(int l, int r, int l1, int r1) {
        if (r - l != r1 - l1) return false;
        if (r < l || r1 < l1) return false;
        return prodS(l, r) == prodT(l1, r1);
    }
    // 　1番目のハッシュ値を返す
    ll HASH_S() { return a; }
    // 　2番目のハッシュ値を返す
    ll HASH_T() { return b; }
    // 全てのハッシュの変換
    vector<ll> ALL_HASH() { return HASH; }
};

}  // namespace rolling_hash_on_segtree_INVAl
   // namespace rolling_hash_on_segtree_INVAl
using rolling_hash_on_segtree_INVAl::rolling_hash_on_segtree;

template <typename mint>
struct FormalPowerSeries : vector<mint> {
    using vector<mint>::vector;
    using FPS = FormalPowerSeries;

    FPS& operator+=(const FPS& r) {
        if (r.size() > this->size()) this->resize(r.size());
        for (int i = 0; i < (int)r.size(); i++) (*this)[i] += r[i];
        return *this;
    }

    FPS& operator+=(const mint& r) {
        if (this->empty()) this->resize(1);
        (*this)[0] += r;
        return *this;
    }

    FPS& operator-=(const FPS& r) {
        if (r.size() > this->size()) this->resize(r.size());
        for (int i = 0; i < (int)r.size(); i++) (*this)[i] -= r[i];
        return *this;
    }

    FPS& operator-=(const mint& r) {
        if (this->empty()) this->resize(1);
        (*this)[0] -= r;
        return *this;
    }

    FPS& operator*=(const mint& v) {
        for (int k = 0; k < (int)this->size(); k++) (*this)[k] *= v;
        return *this;
    }

    FPS& operator/=(const FPS& r) {
        if (this->size() < r.size()) {
            this->clear();
            return *this;
        }
        int n = this->size() - r.size() + 1;
        if ((int)r.size() <= 64) {
            FPS f(*this), g(r);
            g.shrink();
            mint coeff = g.back().inverse();
            for (auto& x : g) x *= coeff;
            int deg = (int)f.size() - (int)g.size() + 1;
            int gs = g.size();
            FPS quo(deg);
            for (int i = deg - 1; i >= 0; i--) {
                quo[i] = f[i + gs - 1];
                for (int j = 0; j < gs; j++) f[i + j] -= quo[i] * g[j];
            }
            *this = quo * coeff;
            this->resize(n, mint(0));
            return *this;
        }
        return *this = ((*this).rev().pre(n) * r.rev().inv(n)).pre(n).rev();
    }

    FPS& operator%=(const FPS& r) {
        *this -= *this / r * r;
        shrink();
        return *this;
    }

    FPS operator+(const FPS& r) const { return FPS(*this) += r; }
    FPS operator+(const mint& v) const { return FPS(*this) += v; }
    FPS operator-(const FPS& r) const { return FPS(*this) -= r; }
    FPS operator-(const mint& v) const { return FPS(*this) -= v; }
    FPS operator*(const FPS& r) const { return FPS(*this) *= r; }
    FPS operator*(const mint& v) const { return FPS(*this) *= v; }
    FPS operator/(const FPS& r) const { return FPS(*this) /= r; }
    FPS operator%(const FPS& r) const { return FPS(*this) %= r; }
    FPS operator-() const {
        FPS ret(this->size());
        for (int i = 0; i < (int)this->size(); i++) ret[i] = -(*this)[i];
        return ret;
    }

    void shrink() {
        while (this->size() && this->back() == mint(0)) this->pop_back();
    }

    FPS rev() const {
        FPS ret(*this);
        reverse(begin(ret), end(ret));
        return ret;
    }

    FPS dot(FPS r) const {
        FPS ret(min(this->size(), r.size()));
        for (int i = 0; i < (int)ret.size(); i++) ret[i] = (*this)[i] * r[i];
        return ret;
    }

    // 前 sz 項を取ってくる。sz に足りない項は 0 埋めする
    FPS pre(int sz) const {
        FPS ret(begin(*this), begin(*this) + min((int)this->size(), sz));
        if ((int)ret.size() < sz) ret.resize(sz);
        return ret;
    }

    FPS operator>>(int sz) const {
        if ((int)this->size() <= sz) return {};
        FPS ret(*this);
        ret.erase(ret.begin(), ret.begin() + sz);
        return ret;
    }

    FPS operator<<(int sz) const {
        FPS ret(*this);
        ret.insert(ret.begin(), sz, mint(0));
        return ret;
    }

    FPS diff() const {
        const int n = (int)this->size();
        FPS ret(max(0, n - 1));
        mint one(1), coeff(1);
        for (int i = 1; i < n; i++) {
            ret[i - 1] = (*this)[i] * coeff;
            coeff += one;
        }
        return ret;
    }

    FPS integral() const {
        const int n = (int)this->size();
        FPS ret(n + 1);
        ret[0] = mint(0);
        if (n > 0) ret[1] = mint(1);
        auto mod = mint::get_mod();
        for (int i = 2; i <= n; i++) ret[i] = (-ret[mod % i]) * (mod / i);
        for (int i = 0; i < n; i++) ret[i + 1] *= (*this)[i];
        return ret;
    }

    mint eval(mint x) const {
        mint r = 0, w = 1;
        for (auto& v : *this) r += w * v, w *= x;
        return r;
    }

    FPS log(int deg = -1) const {
        assert(!(*this).empty() && (*this)[0] == mint(1));
        if (deg == -1) deg = (int)this->size();
        return (this->diff() * this->inv(deg)).pre(deg - 1).integral();
    }

    FPS pow(int64_t k, int deg = -1) const {
        const int n = (int)this->size();
        if (deg == -1) deg = n;
        if (k == 0) {
            FPS ret(deg);
            if (deg) ret[0] = 1;
            return ret;
        }
        for (int i = 0; i < n; i++) {
            if ((*this)[i] != mint(0)) {
                mint rev = mint(1) / (*this)[i];
                FPS ret = (((*this * rev) >> i).log(deg) * k).exp(deg);
                ret *= (*this)[i].pow(k);
                ret = (ret << (i * k)).pre(deg);
                if ((int)ret.size() < deg) ret.resize(deg, mint(0));
                return ret;
            }
            if (__int128_t(i + 1) * k >= deg) return FPS(deg, mint(0));
        }
        return FPS(deg, mint(0));
    }

    static void* ntt_ptr;
    static void set_fft();
    FPS& operator*=(const FPS& r);
    void ntt();
    void intt();
    void ntt_doubling();
    static int ntt_pr();
    FPS inv(int deg = -1) const;
    FPS exp(int deg = -1) const;
};
template <typename mint>
void* FormalPowerSeries<mint>::ntt_ptr = nullptr;

/**
 * @brief 多項式/形式的冪級数ライブラリ
 * @docs docs/fps/formal-power-series.md
 */

template <typename mint>
mint LinearRecurrence(long long k, FormalPowerSeries<mint> Q,
                      FormalPowerSeries<mint> P) {
    Q.shrink();
    mint ret = 0;
    if (P.size() >= Q.size()) {
        auto R = P / Q;
        P -= R * Q;
        P.shrink();
        if (k < (int)R.size()) ret += R[k];
    }
    if ((int)P.size() == 0) return ret;

    FormalPowerSeries<mint>::set_fft();
    if (FormalPowerSeries<mint>::ntt_ptr == nullptr) {
        P.resize((int)Q.size() - 1);
        while (k) {
            auto Q2 = Q;
            for (int i = 1; i < (int)Q2.size(); i += 2) Q2[i] = -Q2[i];
            auto S = P * Q2;
            auto T = Q * Q2;
            if (k & 1) {
                for (int i = 1; i < (int)S.size(); i += 2) P[i >> 1] = S[i];
                for (int i = 0; i < (int)T.size(); i += 2) Q[i >> 1] = T[i];
            } else {
                for (int i = 0; i < (int)S.size(); i += 2) P[i >> 1] = S[i];
                for (int i = 0; i < (int)T.size(); i += 2) Q[i >> 1] = T[i];
            }
            k >>= 1;
        }
        return ret + P[0];
    } else {
        int N = 1;
        while (N < (int)Q.size()) N <<= 1;

        P.resize(2 * N);
        Q.resize(2 * N);
        P.ntt();
        Q.ntt();
        vector<mint> S(2 * N), T(2 * N);

        vector<int> btr(N);
        for (int i = 0, logn = __builtin_ctz(N); i < (1 << logn); i++) {
            btr[i] = (btr[i >> 1] >> 1) + ((i & 1) << (logn - 1));
        }
        mint dw = mint(FormalPowerSeries<mint>::ntt_pr())
                      .inverse()
                      .pow((mint::get_mod() - 1) / (2 * N));

        while (k) {
            mint inv2 = mint(2).inverse();

            // even degree of Q(x)Q(-x)
            T.resize(N);
            for (int i = 0; i < N; i++)
                T[i] = Q[(i << 1) | 0] * Q[(i << 1) | 1];

            S.resize(N);
            if (k & 1) {
                // odd degree of P(x)Q(-x)
                for (auto& i : btr) {
                    S[i] = (P[(i << 1) | 0] * Q[(i << 1) | 1] -
                            P[(i << 1) | 1] * Q[(i << 1) | 0]) *
                           inv2;
                    inv2 *= dw;
                }
            } else {
                // even degree of P(x)Q(-x)
                for (int i = 0; i < N; i++) {
                    S[i] = (P[(i << 1) | 0] * Q[(i << 1) | 1] +
                            P[(i << 1) | 1] * Q[(i << 1) | 0]) *
                           inv2;
                }
            }
            swap(P, S);
            swap(Q, T);
            k >>= 1;
            if (k < N) break;
            P.ntt_doubling();
            Q.ntt_doubling();
        }
        P.intt();
        Q.intt();
        return ret + (P * (Q.inv()))[k];
    }
}

template <typename mint>
mint kitamasa(long long N, FormalPowerSeries<mint> Q,
              FormalPowerSeries<mint> a) {
    assert(!Q.empty() && Q[0] != 0);
    if (N < (int)a.size()) return a[N];
    assert((int)a.size() >= int(Q.size()) - 1);
    auto P = a.pre((int)Q.size() - 1) * Q;
    P.resize(Q.size() - 1);
    return LinearRecurrence<mint>(N, Q, P);
}

/**
 * @brief 線形漸化式の高速計算
 * @docs docs/fps/kitamasa.md
 */
#include <bits/stdc++.h>
using namespace std;
#include <atcoder/all>
#include <cassert>
#include <cmath>
#include <functional>
#include <iostream>
__int128_t Power(__int128_t a, __int128_t b, __int128_t m) {
    __int128_t p = a, Answer = 1;
    for (int i = 0; i < 63; i++) {
        __int128_t wari = (1LL << i);
        if ((b / wari) % 2 == 1) {
            Answer %= m;
            Answer = (Answer * p) % m;  // 「a の 2^i 乗」が掛けられるとき
        }
        p %= m;
        p = (p * p) % m;
    }
    return Answer;
}
// ミラーラビン素数判定法(10**18以下の素数までなら判定可能)
bool is_prime(long long N) {
    if (N <= 1) return false;
    if (N == 2 || N == 3) return true;
    if (N % 2 == 0) return false;
    vector<long long> A = {2, 325, 9375, 28178, 450775, 9780504, 1795265022};
    long long s = 0, d = N - 1;
    while (d % 2 == 0) {
        ++s;
        d >>= 1;
    }
    for (auto a : A) {
        if (a % N == 0) return true;
        long long t, x = Power(a, d, N);
        if (x != 1) {
            for (t = 0; t < s; ++t) {
                if (x == N - 1) break;
                x = __int128_t(x) * x % N;
            }
            if (t == s) return false;
        }
    }
    return true;
}

#endif