#include <bits/stdc++.h>
#define mod 1000000007
#define MOD 998244353
using namespace std;
int Fib(int x)
{
    if (x == 1) return 1;
    return Fib(x - 1) + Fib(x - 2);
}
int S(int x)
{
    int box[15];
    int temp = x,sum = 0,i = 0;
    while (temp != 0)
    {
        box[i] = temp % 10;
        sum++;
        i++;
        temp /= 10;
    }
    int plus = 1,all = 0;
    for (int i = 0; i < sum; i++)
    {
        all += plus * box[i];
        plus *= 10;
    }
    return all;
}
int main()
{
	int t;
	cin >> t;
	int n,ans[t],l = 0;
	for (int i = 0; i < t; i++) cin >> n;
    for (int i = 0; i < t; i++)
	{
	    for (int j = 1; j <= n; j++)
	        l += S(Fib(j));
        l = l % 9;
        ans[i] = l;
    }
    for (int i = 0; i < t; i++)
        cout << ans[i] << endl;
	return 0;
}

MLE(Memory Limit Error) 求助！