#include<iostream>
#include<string>
#include<iomanip>
#include<cmath>
#include<deque>
#include<map>
#include<algorithm>
#include<cctype>
using namespace std;
map<string, int> x;
deque<pair<string, int>> r;
struct m {
	int a;
	int b;
	int min;
	int max;
};
deque<string>yz;
bool cmp1(m x, m y) {
	return x.min < y.min;
	}
bool cmp(m x, m y) {
	if(x.max == y. max)
		return cmp1(x, y);
	return x.max < y.max;
}
int main() {
	int t;
	cin >> t;
	while(t--) {
		int n;
		cin >> n;
		int i, j;
		int sum = 1;
		if(n == 1)
			cout << 1;
		else { 
			for(i = 2; i <= n; i++) {
				int temp = i, sum1 = i;
				for(j = 2; j <= 100; j++) {
					sum1 = (sum1 % 3) * (temp % 3);
					if(sum1 == 0)
						break;
				}
				sum = sum + sum1;
		}
			cout << sum % 3;
		}
		
		if(t != 0)
			cout << endl;
	}
	return 0;
}