#include <iostream>
 
using namespace std;
 
int main() {
    int t;
    cin >> t;
    for(int i = 0; i < t; i++)
    {
        int n;
        cin >> n;
        cout << (3 - n % 3) % 3 << endl;
    }
}

#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
  int t;
  cin >> t;
  while (t--) {
    int n, k;
    string s;
    cin >> n >> k >> s;
    int a = count(s.begin(), s.end(), '0');
    int b = count(s.begin(), s.end(), '1');
    int c = count(s.begin(), s.end(), '2');
    string ans(n, '+');
    for (int i = 0; i < n; ++i) {
      if (i < a + c || i >= n - b - c) ans[i] = '?';
      if (i < a || i >= n - b || k == n) ans[i] = '-';
    }
    cout << ans << '\n';
  }
}

#include <bits/stdc++.h>
 
using namespace std;
 
#define forn(i, n) for(int i = 0; i < int(n); i++) 
 
void solve() {                    
    int n;
    string s;
    cin >> n >> s;
    int cur = count(s.begin(), s.end(), 'a') - count(s.begin(), s.end(), 'b');
    map<int, int> lst;
    int pr = 0;
    lst[pr] = -1;
    int ans = n;
    forn(i, n){
        pr += s[i] == 'a' ? 1 : -1;
        lst[pr] = i;
        if (lst.count(pr - cur))
            ans = min(ans, i - lst[pr - cur]);
    }
    cout << (ans == n ? -1 : ans) << '\n';
}
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t;
    cin >> t;
    forn(i, t) solve();
}

t = int(input())
for i in range(t):
    n, k = map(int, input().split())
    maxk = n * (n - 1) // 2
    dp = [[False for i in range(maxk + 1)] for j in range(n + 1)]
    p = [[-1 for i in range(maxk + 1)] for j in range(n + 1)]
    dp[0][0] = True
    for j in range(n):
        for x in range(maxk + 1):
            for y in range(1, n - j + 1):
                if not dp[j][x]:
                    continue
                add = y * (y - 1) // 2
                dp[j + y][x + add] = True
                p[j + y][x + add] = y
    k = maxk - k
    if dp[n][k]:
        ans = []
        cur = n
        curk = k
        while cur != 0:
            y = p[cur][curk]
            ans.append(y)
            curk -= y * (y - 1) // 2
            cur -= y
        res = []
        cur = n + 1
        for y in ans:
            for x in range(cur - y, cur):
                res.append(x)
            cur -= y
        print(*res)
    else:
        print(0)

#include<bits/stdc++.h>
 
using namespace std;
 
#define fore(i, l, r) for(int i = int(l); i < int(r); i++)
#define sz(a) int((a).size())
 
#define x first
#define y second
 
typedef long long li;
typedef long double ld;
typedef pair<int, int> pt;
 
template<class A, class B> ostream& operator <<(ostream& out, const pair<A, B> &p) {
    return out << "(" << p.x << ", " << p.y << ")";
}
template<class A> ostream& operator <<(ostream& out, const vector<A> &v) {
    fore(i, 0, sz(v)) {
        if(i) out << " ";
        out << v[i];
    }
    return out;
}
 
const int INF = int(1e9);
const li INF64 = li(1e18);
const ld EPS = 1e-9;
 
int ac, dr;
int n;
vector<int> a, d;
 
inline bool read() {
    if(!(cin >> ac >> dr))
        return false;
    cin >> n;
    a.resize(n);
    fore (i, 0, n)
        cin >> a[i];
    d.resize(n);
    fore (i, 0, n)
        cin >> d[i];
    return true;
}
 
vector<int> Tadd, Tmin;
 
void push(int v) {
    Tadd[2 * v + 1] += Tadd[v];
    Tadd[2 * v + 2] += Tadd[v];
    Tadd[v] = 0;
}
 
int getmin(int v) {
    return Tmin[v] + Tadd[v];
}
 
void upd(int v) {
    Tmin[v] = min(getmin(2 * v + 1), getmin(2 * v + 2));
}
 
void init(int v, int l, int r) {
    if (l + 1 == r) {
        Tmin[v] = -l;
        return;
    }
    int mid = (l + r) >> 1;
    init(2 * v + 1, l, mid);
    init(2 * v + 2, mid, r);
    upd(v);
}
 
void init(int n) {
    Tadd.assign(4 * n, 0);
    Tmin.resize(4 * n);
    init(0, 0, n);
}
 
void addVal(int v, int l, int r, int lf, int rg, int val) {
    if (l == lf && r == rg) {
        Tadd[v] += val;
        return;
    }
    int mid = (l + r) >> 1;
    push(v);
    if (lf < mid)
        addVal(2 * v + 1, l, mid, lf, min(mid, rg), val);
    if (rg > mid)
        addVal(2 * v + 2, mid, r, max(lf, mid), rg, val);
    upd(v);
}
 
int firstNeg(int v, int l, int r) {
    if (l + 1 == r) {
        assert(getmin(v) < 0);
        return l;
    }
    push(v);
    int mid = (l + r) >> 1;
    int ans = -1;
    if (getmin(2 * v + 1) < 0)
        ans = firstNeg(2 * v + 1, l, mid);
    else
        ans = firstNeg(2 * v + 2, mid, r);
    upd(v);
    return ans;
}
 
int calcDemand(int i) {
    return min(n, max(a[i] - ac, 0) + max(d[i] - dr, 0));
}
 
inline void solve() {
    init(n + 2);
    fore (i, 0, n) {
        int p = calcDemand(i);
        addVal(0, 0, n + 2, p + 1, n + 2, 1);
    }
 
    int m; cin >> m;
    fore (j, 0, m) {
        int k, na, nd;
        cin >> k >> na >> nd;
        k--;
        int p = calcDemand(k);
        addVal(0, 0, n + 2, p + 1, n + 2, -1);
        a[k] = na;
        d[k] = nd;
        p = calcDemand(k);
        addVal(0, 0, n + 2, p + 1, n + 2, 1);
 
        int ans = firstNeg(0, 0, n + 2);
        cout << ans - 1 << '\n';
    }
}
 
int main() {
#ifdef _DEBUG
    freopen("input.txt", "r", stdin);
    int tt = clock();
#endif
    ios_base::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cout << fixed << setprecision(15);
    
    if(read()) {
        solve();
        
#ifdef _DEBUG
        cerr << "TIME = " << clock() - tt << endl;
        tt = clock();
#endif
    }
    return 0;
}

#include <bits/stdc++.h>
 
using namespace std;
 
using li = long long;
 
const int N = 10;
const int LOG = 50;
const int LCM = 2520;
 
int n;
li m;
int a[N], b[N];
li go[LOG][N][LCM];
 
void solve() {
  cin >> n >> m;
  for (int i = 0; i < n; ++i) cin >> a[i];
  for (int i = 0; i < n; ++i) cin >> b[i];
  for (int x = 0; x < n; ++x) {
    for (int y = 0; y < LCM; ++y) {
      go[0][x][y] = ((y + 1) % a[x]) != b[x];
    }
  }
  for (int i = 1; i < LOG; ++i) {
    for (int x = 0; x < n; ++x) {
      for (int y = 0; y < LCM; ++y) {
        go[i][x][y] = go[i - 1][x][y] + go[i - 1][(x + (1LL << (i - 1))) % n][(y + go[i - 1][x][y]) % LCM];  
      }
    }
  }
  if (go[LOG - 1][0][0] < m) {
    cout << -1 << endl;
    return;
  }
  li s = 0, ans = 0;
  for (int i = LOG - 1; i >= 0; --i) {
    if (s + go[i][ans % n][s % LCM] < m) {
      s += go[i][ans % n][s % LCM];
      ans += 1LL << i;
    }
  }
  cout << ans + 1 << endl;
}
 
int main() {
  int t;
  cin >> t;
  while (t--) solve();
}

#include<bits/stdc++.h>
 
using namespace std;
 
int n, m, k;
 
const int N = 4043;
const int MOD = 998244353;
 
int add(int x, int y)
{
    x += y;
    while(x >= MOD) x -= MOD;
    while(x < 0) x += MOD;
    return x;
}   
 
int sub(int x, int y)
{
    return add(x, -y);
}
 
int mul(int x, int y)
{
    return (x * 1ll * y) % MOD;
}
 
int binpow(int x, int y)
{
    int z = 1;
    while(y > 0)
    {
        if(y % 2 == 1) z = mul(z, x);
        x = mul(x, x);
        y /= 2;
    }
    return z;
}
 
int fact[N];
int rfact[N];
 
void precalc_factorials()
{
    fact[0] = 1;
    for(int i = 1; i < N; i++)
        fact[i] = mul(fact[i - 1], i);
    for(int i = 0; i < N; i++)
        rfact[i] = binpow(fact[i], MOD - 2);
}
 
int choose(int x, int y)
{
    if(x < 0 || y < 0 || x < y) return 0;
    return mul(fact[x], mul(rfact[y], rfact[x - y]));
}
 
vector<int> prefix_sum(const vector<int>& a)
{
    int n = a.size();
    vector<int> p(n + 1);
    for(int i = 0; i < n; i++) p[i + 1] = add(a[i], p[i]);
    return p;
}
 
int get(const vector<int>& a, int i)
{
    if(a.size() > i) return a[i];
    else return a.back();
}   
 
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, m, k;
    cin >> n >> m >> k;
    precalc_factorials();
 
    vector<vector<int>> A(k, vector<int>(n + m));
    for(int x = 0; x < k; x++)
    {
        vector<int> by_rows(n + 1);
        for(int i = 1; i <= n; i++)
            by_rows[i] = mul(choose(n, i), binpow(x, n - i));
        vector<int> pr = prefix_sum(by_rows);
 
        vector<int> by_cols(m + 1);
        for(int i = 1; i <= m; i++)
            by_cols[i] = mul(choose(m, i), binpow(x, m - i));
        vector<int> pc = prefix_sum(by_cols);
 
        for(int i = 1; i <= max(n, m); i++)
        {
            A[x][n + m - i] = sub(mul(get(pr, i + 1), get(pc, i + 1)), mul(get(pr, i), get(pc, i)));
        }     
    }
 
    for(int i = min(n, m); i < n + m; i++)
    {
        int ans = 0;
        for(int j = 0; j < k; j++)
        {
            int cur = mul(choose(k - 1, j), A[k - 1 - j][i]);
            if(j % 2 == 0)
                ans = add(ans, cur);
            else
                ans = add(ans, -cur);
        }
        cout << ans << " ";
    }
    cout << endl;
}