#include <bits/stdc++.h>

using namespace std;
const int N = 1e7 + 50;
int a[N];

int main() {
    a[1] = 1, a[2] = a[3] = 2;
    int grp = 3, prev = 2;
    for (int i = 4; i < N; grp++)
        for (int j = 1; j <= a[grp]; j++, i++) {
            a[i] = 3 - prev;
            if (j == a[grp])
                prev = a[i];
        }
    int T, n;
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);
        printf("%d\n", a[n]);
    }
    return 0;
}