Partial C++ Template

// Author : Naveen
// Program Start
// Libraries and Namespace Start
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
// Libraries and Namespace End

//------------------------------------------------------------------------------------------

// Important Shortcuts Start
// Macros Start
#define F first
#define S second
#define pb push_back
#define yes cout << "yes\n"
#define no cout << "no\n"
#define Yes cout << "Yes\n"
#define No cout << "No\n"
#define YES cout << "YES\n"
#define NO cout << "NO\n"
#define fri(i, s, e) for (ll i = s; i < e; ++i)
#define frd(i, e, s) for(ll i = e; i > s; --i)
#define all(v) v.begin(), v.end()
// Macros End

// Custom Hash Function Start
struct custom_hash {
    static uint64_t splitMix64(uint64_t x) {
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }
    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitMix64(x + FIXED_RANDOM);
    }
};
// Custom Hash Function End

// Declarations Start
typedef bool bl;
typedef long long int ll;
typedef unsigned long long int ull;
typedef long double ld;
typedef string str;
typedef pair<ll, ll> prll;
typedef tuple<ll, ll, ll> tupll;
typedef stack<ll> stkll;
typedef queue<ll> quell;
typedef vector<bl> vecbl;
typedef vector<ll> vecll;
typedef vector<prll> vecprll;
typedef vector<tupll> vectupll;
typedef vector<ld> vecld;
typedef set<ll> setll;
typedef multiset<ll> mltsetll;
typedef map<ll, ll> mapll;
typedef multimap<ll, ll> mltmapll;
// Declarations End

// Using Declarations Start
template <typename T>
using unord_set = unordered_set<T, custom_hash>;
typedef unord_set<ll> unsetll;

template <typename T>
using unord_multiset = unordered_multiset<T, custom_hash>;
typedef unord_multiset<ll> unmltsetll;

template <typename T1, typename T2>
using unord_map = unordered_map<T1, T2, custom_hash>;
typedef unord_map<ll, ll> unmapll;

template <typename T1, typename T2>
using unord_multimap = unordered_multimap<T1, T2, custom_hash>;
typedef unord_multimap<ll, ll> unmltmapll;

template <typename T, typename Compare = greater<T>>
using heap = priority_queue<T, vector<T>, Compare>;
typedef heap<ll> minheapll;
typedef heap<prll> minheapprll;
typedef heap<ll, less<ll>> maxheapll;
typedef heap<prll, less<prll>> maxheapprll;

template <typename T, typename Compare = less<T>>
using pbds_tree = tree<T, null_type, Compare, rb_tree_tag, tree_order_statistics_node_update>;
typedef pbds_tree<ll> pbdssetll;
typedef pbds_tree<ll, less_equal<ll>> pbdsmltsetll;
typedef pbds_tree<prll> pbdsmapll;
typedef pbds_tree<prll, less_equal<prll>> pbdsmltmapll;
// Using Declarations End
// Important Shortcuts End

//------------------------------------------------------------------------------------------

// Important Functions Start
// Constants Start
const ll inf = 9223372036854775807ll;
const ll neg_inf = -9223372036854775807ll - 1ll;
const ll mod1 = 1000000007ll;
const ll mod2 = 998244353ll;
const ll max_if = 200000ll;
const ll one = 1ll;
const ll zero = 0ll;
const str spc = " ";
const str emp = "";
const str newl = "\n";
// Constants End

// Input and Output Functions Start
template <class U, class T>
U& operator>>(U& is, vector<T>& a) {
    for (T& x : a) {
        is >> x;
    }
    return is;
}

template <class U, class T>
U& operator<<(U& os, vector<T>& a) {
    for (ll i = 0;i < a.size();++i) {
        os << a[i] << (i != a.size() - 1 ? spc : emp);
    }
    return os;
}

inline void yn(const bool con) {
    cout << (con ? "yes" : "no") << '\n';
}
inline void Yn(const bool con) {
    cout << (con ? "Yes" : "No") << '\n';
}
inline void YN(const bool con) {
    cout << (con ? "YES" : "NO") << '\n';
}
// Input and Output Functions End

// Debug Functions Start
template<class T>
void debug(const T v) {
    cerr << v;
}

template <class T, class V>
void debug(const pair<T, V>& p) {
    cerr << "(" << p.first << ", " << p.second << ")";
}

template <size_t Index, typename... lls>
typename enable_if<Index == sizeof...(lls)>::type
print_tuple(ostream& os, const tuple<lls...>&) {}

template <size_t Index, typename... lls>
typename enable_if < Index<sizeof...(lls)>::type
    print_tuple(ostream& os, const tuple<lls...>& t) {
    os << get<Index>(t);
    if (Index + 1 < sizeof...(lls)) os << ", ";
    print_tuple<Index + 1>(os, t);
}


template <typename... lls>
void debug(const tuple<lls...>& t) {
    cerr << "(";
    print_tuple<0>(cerr, t);
    cerr << ")";
}

template <class T>
void debug(const vector<T>& vec) {
    size_t c = 0;
    const size_t n = vec.size();
    cerr << "[";
    for (T i : vec) {
        debug(i);
        cerr << (++c < n ? ", " : "");
    }
    cerr << "]\n";
}

template <class T>
void debug(const set<T>& set_v) {
    size_t c = 0;
    const size_t n = set_v.size();
    cerr << "{";
    for (T i : set_v) {
        debug(i);
        cerr << (++c < n ? ", " : "");
    }
    cerr << "}";
}

template <class T>
void debug(const unordered_set<T>& set_v) {
    size_t c = 0;
    const size_t n = set_v.size();
    cerr << "{";
    for (T i : set_v) {
        debug(i);
        cerr << (++c < n ? ", " : "");
    }
    cerr << "}";
}

template <class T>
void debug(const multiset<T>& set_v) {
    size_t c = 0;
    const size_t n = set_v.size();
    cerr << "{";
    for (T i : set_v) {
        debug(i);
        cerr << (++c < n ? ", " : "");
    }
    cerr << "}";
}

template <class T>
void debug(const unordered_multiset<T>& set_v) {
    size_t c = 0;
    const size_t n = set_v.size();
    cerr << "{";
    for (T i : set_v) {
        debug(i);
        cerr << (++c < n ? ", " : "");
    }
    cerr << "}";
}

template <typename T, typename Compare = less<T>>
void debug(const pbds_tree<T, Compare>& set_v) {
    size_t c = 0;
    const size_t n = set_v.size();
    cerr << "{";
    for (T i : set_v) {
        debug(i);
        cerr << (++c < n ? ", " : "");
    }
    cerr << "}";
}

template <class T, class V>
void debug(const map<T, V>& dict) {
    size_t c = 0;
    const size_t n = dict.size();
    cerr << "{";
    for (auto it : dict) {
        debug(it.first);
        cerr << ": ";
        debug(it.second);
        cerr << (++c < n ? ", " : "");
    }
    cerr << "}";
}

template <class T, class V>
void debug(const multimap<T, V>& dict) {
    size_t c = 0;
    const size_t n = dict.size();
    cerr << "{";
    for (auto it : dict) {
        debug(it.first);
        cerr << ": ";
        debug(it.second);
        cerr << (++c < n ? ", " : "");
    }
    cerr << "}";
}

template <class T, class V>
void debug(const unordered_map<T, V>& dict) {
    size_t c = 0;
    const size_t n = dict.size();
    cerr << "{";
    for (auto it : dict) {
        debug(it.first);
        cerr << ": ";
        debug(it.second);
        cerr << (++c < n ? ", " : "");
    }
    cerr << "}";
}

template <class T, class V>
void debug(const unordered_multimap<T, V>& dict) {
    size_t c = 0;
    const size_t n = dict.size();
    cerr << "{";
    for (auto it : dict) {
        debug(it.first);
        cerr << ": ";
        debug(it.second);
        cerr << (++c < n ? ", " : "");
    }
    cerr << "}";
}

template <typename T, typename... Args>
void debug(const T& v, const Args&... args) {
    debug(v);
    debug(args...);
}
// Debug Functions End
// Important Functions End

//------------------------------------------------------------------------------------------

// Basic Functions Start
// String Operator Overload Start
template <class T>
str operator*(const str& s, const T& n) {
    str res;
    res.reserve(s.size() * n);
    for (ll i = 0; i < n; ++i) res += s;
    return res;
}
// String Operator Overload End

//Binary Search Start
template <typename T>
inline ll bin_search(const vector<T>& v, T x) {
    auto it = lower_bound(v.begin(), v.end(), x);
    if (it != v.end() && *it == x) return distance(v.begin(), it);
    return -1;
}
// Binary Search End

// Min Function Start
template <class T>
inline T min(const vector<T>& vec) {
    assert(vec.size() >= 1 && "Cannot find minimum of an empty vector.");
    return *min_element(vec.begin(), vec.end());
}
// Min Function End

// Max Function Start
template <class T>
inline T max(const vector<T>& vec) {
    assert(vec.size() >= 1 && "Cannot find minimum of an empty vector.");
    return *max_element(vec.begin(), vec.end());
}
// Max Function End

// Sum Function Start
template <class T>
inline T sum(T v) {
    return v;
}
template <class T>
inline T sum(T v1, T v2) {
    return v1 + v2;
}
template <class T>
T sum(const initializer_list<T>& ilist) {
    T sumi = T();
    for (const T& val : ilist) sumi += val;
    return sumi;
}
template <class T>
T sum(const vector<T>& vec) {
    T sumi = T();
    for (auto i : vec) sumi += sum(i);
    return sumi;
}
template <class T>
T sum(const set<T>& seti) {
    T sumi = T();
    for (auto i : seti) sumi += sum(i);
    return sumi;
}
template <class T>
T sum(const multiset<T>& seti) {
    T sumi = T();
    for (auto i : seti) sumi += sum(i);
    return sumi;
}
template <typename T, typename Compare = less<T>>
T sum(const pbds_tree<T, Compare>& seti) {
    T sumi = T();
    for (auto i : seti) sumi += sum(i);
    return sumi;
}
// Sum Function End

// Binary Start
template <class T>
str bin(const T& dn) {
    str bin_str = bitset<64>(dn).to_string();
    ll firstOne = bin_str.find('1');
    if (firstOne != str::npos) {
        bin_str = bin_str.substr(firstOne);
        return bin_str;
    }
    return "0";
}

ll int2(const str& bin_str) {
    bitset<64> bits(bin_str);
    ll dn = static_cast<ll>(bits.to_ulong());
    return dn;
}
// Binary End

// Square Root Start
inline ll sqrt_int(ll n) {
    assert(n >= 0 && "The number can't be negative.");
    return static_cast<ll>(sqrt(n));
}

ll sqrt_int_u(ll n) {
    assert(n >= 0 && "The number can't be negative.");
    ll k = sqrt(n);
    return k * k == n ? k : k + 1;
}
// Square Root End

// Map Computation Start
template <class T>
void map_com(map<T, ll>& ma, const vector<T>& vec) {
    for (T i : vec) ma[i]++;
}
// Map Computation End
// Basic Functions End

//------------------------------------------------------------------------------------------

// Algorithms Start
// Power Function Start
ll power(ll a, ll b, const ll mod = mod1) {
    assert(b >= 0 && "Power cannot be negative.");
    ll ans = 1;
    a %= mod;
    while (b) {
        if (b & 1) ans = (ans * a) % mod;
        a = (a * a) % mod;
        b >>= 1;
    }
    return ans;
}
// Power Function End

// Modular Inverse Start
inline ll mod_inv(ll a, const ll mod = mod1) {
    assert(a >= 0 && "The number must be non-negative.");
    return power(a, mod - 2, mod);
}
// Modular Inverse End

// Fast Fib Start
ll fast_fib(ll n, const ll mod = mod1, const bl is_mod = true) {
    assert(n >= 0 && "The numbers can't be negative.");
    ll a0 = 0, a1 = 1, f2, f21, t;
    for (ll i = 61; i >= 0; --i) {
        f2 = a0 * (2 * a1 - a0);
        f21 = a0 * a0 + a1 * a1;
        if (is_mod) {
            f2 %= mod;
            f21 %= mod;
        }
        if (n & (one << i)) {
            a0 = f21;
            a1 = f2 + f21;
            if (is_mod) a1 %= mod;
        }
        else {
            a0 = f2;
            a1 = f21;
        }
    }
    return is_mod ? a0 % mod : a0;
}
// Fast Fib End

// KMP Algorithm Start
ll substr_is_in(const str& text, const str& pattern) {
    const size_t m = pattern.size();
    const size_t n = text.size();
    vecll lps(m, 0);
    ll len = 0, i = 1, j;
    while (i < m) {
        if (pattern[i] == pattern[len]) lps[i++] = ++len;
        else {
            if (len != 0) len = lps[len - 1];
            else lps[i++] = 0;
        }
    }
    i = 0, j = 0;
    while (i < n) {
        if (pattern[j] == text[i]) {
            ++i;
            ++j;
        }
        if (j == m) return i - j;
        else if (i < n && pattern[j] != text[i]) {
            if (j != 0) j = lps[j - 1];
            else ++i;
        }
    }
    return -1;
}
// KMP Algorithm End
// Algorithms End

//------------------------------------------------------------------------------------------

// Classes Start
// Big Int Start
namespace fft {
    const ll mod = -1;
    class cpx {
    public:
        double r, i;
        cpx(double _r = 0, double _i = 0) : r(_r), i(_i) {}
        cpx operator+(cpx b) { return { r + b.r, i + b.i }; }
        cpx operator-(cpx b) { return { r - b.r, i - b.i }; }
        cpx operator*(cpx b) { return { r * b.r - i * b.i, r * b.i + i * b.r }; }
        cpx operator/(double b) { return { r / b, i / b }; }
        inline cpx conj() { return { r, -i }; }
    };
    const double PI = acos(-1);
    vector<ll> rev(1, 0);
    vector<cpx> roots;
    ll base = 0;
    void precompute(ll nbase) {
        if (nbase <= base)
            return;
        rev.resize(1 << nbase);
        for (ll i = 0; i < (1 << nbase); ++i) {
            rev[i] = rev[i >> 1] >> 1 | ((i & 1) << (nbase - 1));
        }
        roots.resize(1 << nbase);
        for (; base < nbase; ++base) {
            ll len = 1 << base;
            double angle = 2 * PI / (1 << (base + 1));
            for (ll i = 0; i < len; ++i) {
                double cur = angle * i;
                roots[len + i] = cpx(cos(cur), sin(cur));
            }
        }
    }
    void fft(vector<cpx>& a, ll n = -1) {
        if (n == -1)
            n = a.size();
        assert((n & (n - 1)) == 0);
        ll zeros = __builtin_ctz(n);
        precompute(zeros);
        ll shift = base - zeros;
        for (ll i = 0; i < n; ++i) {
            if (i < (rev[i] >> shift))
                swap(a[i], a[rev[i] >> shift]);
        }
        for (ll len = 1; len < n; len <<= 1)
            for (ll i = 0; i < n; i += 2 * len)
                for (ll j = 0; j < len; ++j) {
                    cpx u = a[i + j], v = a[i + j + len] * roots[len + j];
                    a[i + j] = u + v;
                    a[i + j + len] = u - v;
                }
    }
    vector<cpx> fa, fb;
    vector<ll> multiply(const vector<ll>& a, const vector<ll>& b) {
        if (a.empty() || b.empty()) return {};
        ll sz = a.size() + b.size() - 1;
        ll n = sz == 1 ? 1 : 1 << (32 - __builtin_clz(sz - 1));
        if (n > fa.size()) fa.resize(n);
        for (ll i = 0; i < n; ++i) {
            ll x = i < a.size() ? a[i] : 0;
            ll y = i < b.size() ? b[i] : 0;
            fa[i] = cpx(x, y);
        }
        fft(fa, n);
        cpx r(0, -0.5 / n);
        for (ll i = 0; i <= (n >> 1); ++i) {
            ll j = (n - i) & (n - 1);
            cpx x = (fa[i] + fa[j].conj()) / 2;
            cpx y = (fa[i] - fa[j].conj()) * r;
            fa[i] = x * y;
            if (i != j) fa[j] = fa[i].conj();
        }
        fft(fa, n);
        reverse(fa.begin() + 1, fa.begin() + n);
        vector<ll> res(sz);
        for (ll i = 0; i < sz; ++i) res[i] = llround(fa[i].r);
        return res;
    }
}

const ll BASE = 1000;
const ll BASE_DIGITS = log10(BASE);

class BigInt {
private:
    bool neg = false;
    vecll num;
public:
    BigInt() {}
    BigInt(const string& s) {
        ll st = 0;
        if (s[0] == '-') {
            neg = true;
            st = 1;
        }
        for (ll i = (ll)s.size() - 1; i >= st; i -= BASE_DIGITS) {
            ll x = 0;
            for (ll j = max(st, i - BASE_DIGITS + 1); j <= i; ++j) x = x * 10 + s[j] - '0';
            num.push_back(x);
        }
        trim();
    }
    BigInt(ll m) {
        if (m < 0) neg = true;
        while (m) {
            num.push_back(abs(m % BASE));
            m /= BASE;
        }
    }

    void trim() {
        while (!num.empty() && !num.back()) num.pop_back();
        if (num.empty()) neg = false;
    }

    bool operator<(const BigInt& v) const {
        if (neg != v.neg) return neg > v.neg;
        if (num.size() != v.num.size()) return neg ? num.size() > v.num.size() : num.size() < v.num.size();
        for (ll i = (ll)num.size() - 1; i >= 0; --i)
            if (num[i] != v.num[i]) return neg ? num[i] > v.num[i] : num[i] < v.num[i];
        return false;
    }
    bool operator>(const BigInt& v) const { return v < *this; }
    bool operator<=(const BigInt& v) const { return !(v < *this); }
    bool operator>=(const BigInt& v) const { return !(*this < v); }
    bool operator==(const BigInt& v) const { return num == v.num && neg == v.neg; }
    bool operator!=(const BigInt& v) const { return !(*this == v); }

    BigInt operator-() const {
        BigInt ret(*this);
        if (!ret.num.empty()) ret.neg = !ret.neg;
        return ret;
    }
    BigInt& operator+=(const BigInt& x) {
        if (neg && !x.neg) return *this = x - (-*this);
        if (!neg && x.neg) return *this -= -x;
        assert(neg == x.neg);
        ll maxs = max(num.size(), x.num.size());
        num.resize(maxs);
        ll carry = 0;
        for (ll i = 0; i < maxs; ++i) {
            ll other = i >= x.num.size() ? 0 : x.num[i];
            num[i] += other + carry;
            carry = num[i] / BASE;
            num[i] %= BASE;
        }
        if (carry) num.push_back(carry);
        return *this;
    }
    BigInt& subtract(const BigInt& x) {
        assert(!neg && !x.neg);
        ll carry = 0;
        for (ll i = 0; i < num.size(); ++i) {
            ll other = i >= x.num.size() ? 0 : x.num[i];
            num[i] -= other + carry;
            carry = num[i] < 0;
            if (carry) num[i] += BASE;
        }
        trim();
        return *this;
    }
    BigInt& operator-=(const BigInt& x) {
        if (neg && !x.neg) return *this = -(-*this + x);
        if (x.neg) return *this += -x;
        assert(!neg && !x.neg);
        if (*this < x) {
            BigInt y = *this;
            *this = x;
            return *this = -subtract(y);
        }
        return subtract(x);
    }
    BigInt& operator*=(ll m) {
        const ll MX = LLONG_MAX / BASE;
        if (m < -MX || m > MX) return *this *= BigInt(m);
        neg ^= m < 0;
        m = abs(m);
        ll carry = 0;
        for (ll i = 0; i < num.size(); ++i) {
            ll v = num[i] * m + carry;
            carry = v / BASE;
            num[i] = v % BASE;
        }
        while (carry) {
            num.push_back(carry % BASE);
            carry /= BASE;
        }
        trim();
        return *this;
    }
    BigInt& operator*=(const BigInt& x) {
        if (num.empty()) return *this;
        neg ^= x.neg;
        auto c = fft::multiply(num, x.num);
        num.resize(c.size());
        ll carry = 0;
        for (ll i = 0; i < c.size(); ++i) {
            c[i] += carry;
            carry = c[i] / BASE;
            num[i] = c[i] % BASE;
        }
        if (carry) num.push_back(carry);
        trim();
        return *this;
    }

    ll divide_and_remainder(ll d) {
        assert(d != 0);
        const ll MX = LLONG_MAX / BASE;
        if (d < -MX || d > MX) return static_cast<ll>(divide_and_remainder(BigInt(d)));
        bool wasNeg = neg;
        neg ^= d < 0;
        d = abs(d);
        ll cur = 0;
        vector<ll> ret(num.size());
        for (ll i = (ll)num.size() - 1; i >= 0; --i) {
            cur *= BASE;
            cur += num[i];
            ret[i] = cur / d;
            cur %= d;
        }
        swap(num, ret);
        trim();
        return wasNeg ? -cur : cur;
    }

    BigInt& operator/=(ll v) {
        divide_and_remainder(v);
        return *this;
    }
    BigInt& operator%=(ll v) {
        ll remainder = divide_and_remainder(v);
        return *this = BigInt(remainder);
    }
    BigInt divide_and_remainder(BigInt b) {
        assert(!b.num.empty());
        bool wasNeg = neg;
        neg ^= b.neg;
        b.neg = false;
        BigInt cur;
        vector<ll> ret(num.size());
        for (ll i = (ll)num.size() - 1; i >= 0; --i) {
            cur *= BASE;
            cur += num[i];
            ll lo = 0, hi = BASE - 1;
            while (lo < hi) {
                ll d = (lo + hi + 1) >> 1;
                if (b * d > cur) hi = d - 1;
                else lo = d;
            }
            cur -= b * lo;
            ret[i] = lo;
        }
        swap(num, ret);
        trim();
        if (wasNeg && !cur.num.empty()) cur.neg = true;
        return cur;
    }
    BigInt& operator/=(const BigInt& x) {
        divide_and_remainder(x);
        return *this;
    }
    BigInt& operator%=(const BigInt& x) { return *this = divide_and_remainder(x); }
    BigInt& operator++() { return *this += 1; }
    BigInt& operator--() { return *this -= 1; }
    BigInt operator++(int) {
        BigInt ret(*this);
        *this += 1;
        return ret;
    }
    BigInt operator--(int) {
        BigInt ret(*this);
        *this -= 1;
        return ret;
    }

    friend BigInt operator+(BigInt a, const BigInt& b) { return a += b; }
    friend BigInt operator-(BigInt a, const BigInt& b) { return a -= b; }
    friend BigInt operator*(ll a, BigInt b) { return b *= a; }
    friend BigInt operator*(BigInt a, ll b) { return a *= b; }
    friend BigInt operator*(BigInt a, const BigInt& b) { return a *= b; }
    friend BigInt operator/(BigInt a, ll b) { return a /= b; }
    friend BigInt operator/(BigInt a, const BigInt& b) { return a /= b; }
    friend BigInt operator%(BigInt a, ll b) { return a %= b; }
    friend BigInt operator%(BigInt a, const BigInt& b) { return a %= b; }

    explicit operator ll() const {
        const unsigned long long MAX_ABS = LLONG_MAX + (unsigned ll)neg;
        const unsigned long long MX = MAX_ABS / BASE;
        unsigned long long ret = 0;
        for (ll i = (ll)num.size() - 1; i >= 0; --i) {
            if (ret > MX) throw;
            ret *= BASE;
            if (ret > MAX_ABS - num[i]) throw;
            ret += num[i];
        }
        assert(ret <= MAX_ABS);
        return neg ? -ret : ret;
    }
    str operator()() const {
        if (num.empty()) return "0";
        str ret;
        if (neg) ret += '-';
        ret += to_string(num.back());
        str fmt = "%0" + to_string(BASE_DIGITS) + "d";
        for (ll i = (ll)num.size() - 2; i >= 0; --i) {
            char buf[BASE_DIGITS + 1];
            sprintf(buf, fmt.c_str(), num[i]);
            ret += buf;
        }
        return ret;
    }

    friend BigInt gcd(const BigInt& a, ll b) {
        if (!b) return abs(a);
        ll r = static_cast<ll>(abs(a % b));
        if (r == 0) return abs(BigInt(b));
        return __gcd(r, abs(b % r));
    }
    friend BigInt gcd(ll a, const BigInt& b) { return gcd(b, a); }
    friend BigInt gcd(BigInt a, BigInt b) {
        a.neg = b.neg = false;
        while (!b.num.empty()) {
            BigInt c(b);
            b = a % b;
            swap(a, c);
        }
        return a;
    }
    friend BigInt rand_big_ll(BigInt n) {
        static mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
        assert(!n.num.empty() && !n.neg);
        n--;
        for (;;) {
            BigInt res;
            res.num.resize(n.num.size());
            for (ll i = (ll)n.num.size() - 1; i >= 0; --i) {
                ll mx = (i + 1 == n.num.size()) ? n.num[i] : BASE - 1;
                res.num[i] = rng() % (mx + 1);
            }
            res.trim();
            if (res <= n) return res;
        }
        assert(false);
    }
    friend BigInt abs(BigInt x) {
        x.neg = false;
        return x;
    }
    template <class U>
    friend U& operator<<(U& os, const BigInt& x) {
        os << x();
        return os;
    }
    template <class U>
    friend U& operator>>(U& is, BigInt& x) {
        str s;
        is >> s;
        x = s;
        return is;
    }
};
BigInt operator""_b(const char* str) {
    BigInt temp(str);
    return temp;
}

typedef BigInt bll;
// Big Int end

// Modular Start
class Modular {
private:
    ll value;
    const ll mod;
    inline void normalize(ll& val) {
        if (val >= mod && val <= -mod) val %= mod;
        if (val < 0) val += mod;
    }

public:
    Modular(ll x = 0, ll m = mod1) : mod(m) {
        normalize(x);
        value = x;
    }
    Modular(const Modular& other) : value(other.value), mod(other.mod) {}
    Modular& operator=(const Modular& other) {
        assert(mod == other.mod && "The mod values have to be the same.");
        if (this != &other) value = other.value;
        return *this;
    }
    Modular& operator=(ll val) {
        normalize(val);
        value = val;
        return *this;
    }

    ll operator()() const {
        return value;
    }
    operator ll() const {
        return value;
    }

    Modular& operator+=(ll val) {
        normalize(val);
        value = (value + val) % mod;
        return *this;
    }
    Modular& operator-=(ll val) {
        normalize(val);
        value = (value - val + mod) % mod;
        return *this;
    }
    Modular& operator*=(ll val) {
        normalize(val);
        value = (value * val) % mod;
        return *this;
    }
    Modular pow(ll p) {
        return Modular(power(this->value, p, this->mod), this->mod);
    }
    Modular mod_in() {
        return Modular(mod_inv(this->value, this->mod), this->mod);
    }
    Modular& operator/=(ll val) {
        value = (value * mod_inv(val, mod)) % mod;
        return *this;
    }
    Modular& operator<<=(ll val) {
        value = (value * power(2, val, mod)) % mod;
        return *this;
    }
    Modular& operator>>=(ll val) {
        value = (value * mod_inv(power(2, val, mod), mod)) % mod;
        return *this;
    }
    Modular& operator++() {
        if (++value >= mod) value -= mod;
        return *this;
    }
    Modular& operator--() {
        if (--value < 0) value += mod;
        return *this;
    }
    Modular operator++(int) {
        Modular ret(*this);
        if (++value >= mod) value -= mod;
        return ret;
    }
    Modular operator--(int) {
        Modular ret(*this);
        if (--value < 0) value += mod;
        return ret;
    }
    Modular operator-() const {
        return Modular(mod - value, mod);
    }
    Modular operator+(ll val) {
        return Modular(*this) += val;
    }
    Modular operator-(ll val) {
        return Modular(*this) -= val;
    }
    Modular operator*(ll val) {
        return Modular(*this) *= val;
    }
    Modular operator/(ll val) {
        return Modular(*this) /= val;
    }
    Modular operator<<(ll val) {
        return Modular(*this) <<= val;
    }
    Modular operator>>(ll val) {
        return Modular(*this) >>= val;
    }

    template <class U>
    friend U& operator<<(U& os, const Modular& num) {
        return os << num.value;
    }
    template <class U>
    friend U& operator>>(U& is, Modular& num) {
        ll x;
        is >> x;
        num.value = (x % num.mod + num.mod) % num.mod;
        return is;
    }
    friend bool operator<(const Modular& lhs, const Modular& rhs) {
        return lhs.value < rhs.value;
    }
    friend bool operator>(const Modular& lhs, const Modular& rhs) {
        return lhs.value > rhs.value;
    }
    friend bool operator<=(const Modular& lhs, const Modular& rhs) {
        return lhs.value <= rhs.value;
    }
    friend bool operator>=(const Modular& lhs, const Modular& rhs) {
        return lhs.value >= rhs.value;
    }
    friend bool operator==(const Modular& lhs, const Modular& rhs) {
        return lhs.value == rhs.value;
    }
    friend bool operator!=(const Modular& lhs, const Modular& rhs) {
        return lhs.value != rhs.value;
    }
};
Modular operator""_m(const char* str) {
    Modular temp(stoll(str), mod1);
    return temp;
}
Modular operator""_m2(const char* str) {
    Modular temp(stoll(str), mod2);
    return temp;
}

typedef Modular mll;
typedef vector<mll> vecmll;
// Modular End


// PNC Start
class PNC {
public:
    const ll size, mod;
    vecll fact, invfact;
    PNC(const ll len = max_if, const ll m = mod1) : size(len), mod(m), fact(size + 1, 1), invfact(size + 1, 0) {
        invfact[0] = mod_inv(fact[0], mod);
        for (ll i = 1; i <= size; ++i) {
            fact[i] = (fact[i - 1] * i) % mod;
            invfact[i] = mod_inv(fact[i], mod);
        }
    }

    ll facto(ll n) {
        assert(n >= 0 && "The number can't be negative.");
        if (n <= size) return fact[n];
        ll ans = 1;
        for (ll i = 1; i <= n; ++i) ans = (ans * i) % mod;
        return ans;
    }

    ll perm(ll n, ll r) {
        assert(n >= 0 && r >= 0 && "The number can't be negative.");
        if (n < r) return 0;
        if (n <= size) return (fact[n] * invfact[n - r]) % mod;
        ll ans = 1;
        for (ll i = n - r + 1; i <= n; ++i) ans = (ans * i) % mod;
        return ans;
    }

    ll comb(ll n, ll r) {
        assert(n >= 0 && r >= 0 && "The number can't be negative.");
        if (n < r) return 0;
        if (n <= size) return (fact[n] * (invfact[n - r] * invfact[r] % mod)) % mod;
        ll num = 1, den = 1;
        if (r > n / 2) r = n - r;
        ++n;
        for (ll i = 1; i <= r; ++i) {
            num = (num * (n - i)) % mod;
            den = (den * i) % mod;
        }
        return (num * mod_inv(den, mod)) % mod;
    }
};
// PNC End

// Prime Start
class Prime {
public:
    ll size;
    vecbl isprime;
    vecll primes;
    Prime(const ll len = max_if) : size(len), isprime(size + 1, true) {
        isprime[0] = isprime[1] = false;
        for (ll i = 2; i <= sqrt_int_u(size); ++i)
            if (isprime[i])
                for (ll j = i * i; j <= size; j += i) isprime[j] = false;
        for (ll i = 2; i <= size; ++i)
            if (isprime[i]) primes.pb(i);
    }

    bool is_prime(ll n, bool old = false) {
        assert(n > 0 && "The given number can't be negative");
        if (n == 1) return false;
        if (n <= 3) return true;
        if (n % 2 == 0 || n % 3 == 0) return false;
        if (n <= size) return isprime[n];
        if (old) {
            for (ll i = 5; i < (int)sqrt(n) + 1; i += 6)
                if (n % i == 0 || n % (i + 2) == 0) return false;
            return true;
        }
        ll d = n - 1;
        while (d % 2 == 0) d /= 2;
        auto miller = [&](ll a) {
            if (a % n == 0) return true;
            ll x = power(a, d, n);
            if (x == 1 || x == n - 1) return true;
            ll c = d;
            while (c < n - 1) {
                x = (x * x) % n;
                if (x == n - 1) return true;
                c <<= 1;
            }
            return false;
            };
        vector<ll> bases64 = { 2, 325, 9375, 28178, 450775, 9780504, 1795265022 };
        vector<ll> bases32 = { 2, 7, 61 };
        vector<ll>& bases = n <= 4294967296ll ? bases32 : bases64;
        for (ll base : bases)
            if (!miller(base)) return false;
        return true;
    }
};
// Prime End

// Polynomial Hashing Start
class PolyHash {
public:
    ll n;
    str s;
    vecll hash, powers, mmi;
    const ll p = 31;
    PolyHash(str& st): n(st.size()), s(st), hash(n, 0), powers(n, 1), mmi(n, 1) {
        for (ll i = 1; i < n; i++) {
            powers[i] = (powers[i - 1] * p) % mod1;
            mmi[i] = mod_inv(powers[i]);
        }
        hash[0] = s[0] - 'a' + 1;
        for (ll i = 1; i < n; i++) hash[i] = (hash[i - 1] + (powers[i] * (s[i] - 'a' + 1) % mod1)) % mod1;
    }

    ll hash_val(ll left, ll right) {
        if (left == 0) return hash[right];
        ll ans = (hash[right] - hash[left - 1] + mod1) % mod1;
        ans = (mmi[left] * ans) % mod1;
        return ans;
    }
};
// Polynomial Hashing End

// Disjoint Set Union Start
class DisjointSet {
private:
    vecll parent, depth, set_size, max_set, min_set;
    ll num_sets, max_size;
public:
    DisjointSet() {}
    DisjointSet(ll n, ll start = 1) { init(n, start); }
    DisjointSet(const DisjointSet& obj) : parent(all(obj.parent)), depth(all(obj.depth)), set_size(all(obj.set_size)), min_set(all(obj.min_set)), max_set(all(obj.max_set)), max_size(obj.max_size), num_sets(obj.num_sets) {}

    void init(ll n, ll start = 1) {
        num_sets = n;
        max_size = 1;
        n += start;
        parent.assign(n, 0);
        max_set.assign(n, 0);
        min_set.assign(n, 0);
        for (ll i = start; i < n; ++i) parent[i] = max_set[i] = min_set[i] = i;
        depth.assign(n, 0);
        set_size.assign(n, 1);
    }
    ll find_set(ll n) {
        return parent[n] = (parent[n] == n ? n : find_set(parent[n]));
    }
    ll find_set(ll n, bool p) {
        stack<ll> st;
        ll v;
        while (n != parent[n]) {
            st.push(n);
            n = parent[n];
        }
        while (!st.empty()) {
            v = st.top();
            st.pop();
            parent[v] = n;
        }
        return n;
    }
    bool is_same_set(ll a, ll b) {
        return find_set(a) == find_set(b);
    }
    void union_set(ll a, ll b) {
        ll x = find_set(a), y = find_set(b);
        if (x == y) return;
        if (depth[x] > depth[y]) swap(x, y);
        if (depth[x] == depth[y]) depth[y]++;
        parent[x] = y;
        set_size[y] += set_size[x];
        max_size = max((ll)max_size, set_size[y]);
        min_set[y] = min(min_set[y], min_set[x]);
        max_set[y] = max(max_set[y], max_set[x]);
        num_sets--;
    }
    ll num_of_sets() { return num_sets; }
    ll size_of_set(ll n) { return set_size[find_set(n)]; }
    ll max_of_set(ll n) { return max_set[find_set(n)]; }
    ll min_of_set(ll n) { return min_set[find_set(n)]; }
    ll max_size_of_sets() { return max_size; }
};
// Disjoint Set Union End

// Unweighted Graph Start
// Unweighted Graph End

// Weighted Graph Start
// Weighted Graph End

// Segment Tree Start
template <class T>
class SegmentTree {
private:
    const function<T(T, T)>& func;
    vector<T> tree;
    const size_t size;
    size_t query_left, query_right, update_index, update_new_value;

    void build_tree(size_t tree_index, size_t left, size_t right) {
        if (left == right) {
            tree[tree_index] = data[left];
            return;
        }
        size_t mid = left + (right - left) / 2;
        build_tree(2 * tree_index + 1, left, mid);
        build_tree(2 * tree_index + 2, mid + 1, right);
        tree[tree_index] = func(tree[2 * tree_index + 1], tree[2 * tree_index + 2]);
    }
    T query(size_t tree_index, size_t left, size_t right) {
        if (query_left <= left && right <= query_right) return tree[tree_index];
        size_t mid = left + (right - left) / 2;
        if (mid < query_left || left > query_right) return query(2 * tree_index + 2, mid + 1, right);
        if (right < query_left || mid + 1 > query_right) return query(2 * tree_index + 1, left, mid);
        return func(query(2 * tree_index + 1, left, mid), query(2 * tree_index + 2, mid + 1, right));
    }
    void update(size_t tree_index, size_t left, size_t right) {
        if (left == right) {
            tree[tree_index] = update_new_value;
            return;
        }
        size_t mid = left + (right - left) / 2;
        if (update_index <= mid) update(2 * tree_index + 1, left, mid);
        else update(2 * tree_index + 2, mid + 1, right);
        tree[tree_index] = func(tree[2 * tree_index + 1], tree[2 * tree_index + 2]);
    }

public:
    vector<T> data;

    SegmentTree(const vector<T>& vec, const function<T(T, T)>& fun) : size(vec.size()), func(fun), data(vec.begin(), vec.end()) {
        tree.resize(4 * size);
        build_tree(0, 0, size - 1);
    }

    T query(ll left, ll right) {
        assert(left >= 0 && right < size && left <= right && "Given query range is invalid or out of range.");
        query_left = left;
        query_right = right;
        return query(0, 0, size - 1);
    }
    void update(ll index, T new_value) {
        assert(index >= 0 && index < size && "Given update index is out of range.");
        data[index] = new_value;
        update_index = index;
        update_new_value = new_value;
        update(0, 0, size - 1);
    }
};
// Segment Tree End

// Trie Start
class Trie {
public:
    ll size;
    ll cnt;
    vecll freq;
    str chars;
    unordered_map<char, ll> mp;
    vector<Trie*> child;

    Trie(const ll len = 26, str s = "abcdefghijklmnopqrstuvwxyz") : size(len), cnt(0), freq(size, 0), chars(s), child(size, nullptr) {
        for (ll i = 0; i < size; i++) mp[chars[i]] = i;
    }

    void insert(str s) {
        Trie* node = this;
        ll n = s.length();
        for (ll i = 0; i < n; i++) {
            ll mask = mp[s[i]];
            node->freq[mask]++;
            if (node->child[mask] == nullptr) node->child[mask] = new Trie();
            node = node->child[mask];
        }
        node->cnt++;
    }
    void remove(str s) {
        Trie* node = this;
        ll n = s.length();
        for (ll i = 0; i < n; i++) {
            ll mask = mp[s[i]];
            node->freq[mask]--;
            if (node->freq[mask] == 0) {
                node->child[mask] = nullptr;
                return;
            }
            node = node->child[mask];
        }
    }
    bool search(str s) {
        Trie* node = this;
        ll n = s.length();
        for (ll i = 0; i < n; i++) {
            ll mask = mp[s[i]];
            if (node->child[mask] == nullptr) return false;
            node = node->child[mask];
        }
        return true;
    }
};
// Trie End

// Monotonic Stack Start
class MonotonicStack {
private:
    const ll n;
    const bl eq_pmn, eq_pmx, eq_nmn, eq_nmx;
    vecll prev_min, prev_max, next_min, next_max;

    inline void check(ll inx) {
        assert(inx >= 0 && inx < n && "Index out of bounds");
    }

public:
    template<class T>
    MonotonicStack(vector<T>& arr, bl eql_pmn = false, bl eql_pmx = false, bl eql_nmn = false, bl eql_nmx = false) : n(arr.size()), eq_pmn(eql_pmn), eq_pmx(eql_pmx), eq_nmn(eql_nmn), eq_nmx(eql_nmx), prev_min(n, -1), prev_max(n, -1), next_min(n, n), next_max(n, n) {
        stack<pair<T, ll>> st1, st2;
        for (ll i = n - 1;i >= 0;--i) {
            while (!st1.empty() && st1.top().F + (eq_pmn ? 1 : 0) > arr[i]) {
                prev_min[st1.top().S] = i;
                st1.pop();
            }
            st1.push({ arr[i], i });
            while (!st2.empty() && st2.top().F < arr[i] + (eq_pmx ? 1 : 0)) {
                prev_max[st2.top().S] = i;
                st2.pop();
            }
            st2.push({ arr[i], i });
        }
        stack<pair<T, ll>>().swap(st1);
        stack<pair<T, ll>>().swap(st2);
        for (ll i = 0;i < n;++i) {
            while (!st1.empty() && st1.top().F + (eq_nmn ? 1 : 0) > arr[i]) {
                next_min[st1.top().S] = i;
                st1.pop();
            }
            st1.push({ arr[i], i });
            while (!st2.empty() && st2.top().F < arr[i] + (eq_nmx ? 1 : 0)) {
                next_max[st2.top().S] = i;
                st2.pop();
            }
            st2.push({ arr[i], i });
        }
    }

    ll prev_min_inx(ll inx) {
        check(inx);
        return prev_min[inx];
    }
    ll prev_max_inx(ll inx) {
        check(inx);
        return prev_max[inx];
    }
    ll next_min_inx(ll inx) {
        check(inx);
        return next_min[inx];
    }
    ll next_max_inx(ll inx) {
        check(inx);
        return next_max[inx];
    }
};
// Monotonic Stack End
// Classes End

//------------------------------------------------------------------------------------------

// Global Variables Start
PNC* pnc;
Prime* prime;

auto func = []() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    // pnc = new PNC();
    // prime = new Prime();
    return 0;
    }();
// Global Variables End

// #define debug(...) 60

// /* // Solution Class Start
class Solution {
public:

    void solve(ll index) {
        //----------------------------------------------------------------------------------

        // debug("Case #",index,": ",newl);
        ll n,i,j,k;
        cin>>n;

        // cout<<"Case #"<<index<<": "<<ans<<newl;

        //----------------------------------------------------------------------------------
    }

    bool test_cases=true;
};
// Solution Class End

//------------------------------------------------------------------------------------------

// Main Function Start
int main() {
    Solution sol;
    ll test_cases = 1;
    if (sol.test_cases) cin >> test_cases;
    for (ll test_case = 1; test_case <= test_cases; ++test_case) sol.solve(test_case);
    return 0;
}
// Main Function End
// */ // Program End
//------------------------------------------------------------------------------------------