#include<bits/stdc++.h>
#define N 1000010
#define mod 9

using namespace std;

typedef long long ll;

ll a[N];

ll fib(ll n)
{
	if (a[n]) return a[n];
	ll k=n;
	n >>= 1;
	if (k%2) return a[k] = fib(n)*fib(n)%mod+fib(n+1)*fib(n+1)%mod;
	else return a[k] = (2*fib(n-1)%mod+fib(n))*fib(n)%mod;
}

ll solve(ll n)
{
	int ans=0;
	while(n!=0)
	{
		int k = n%10;
		ans += k;
		n /= 10;
	}
	return ans;
}

ll read()
{
    ll x = 0,f = 1;
    char c = getchar();
    while(c<'0' || c>'9')
	{
        if(c=='-') f = -1;
        c = getchar();
    }
    while(c>='0' && c<='9')
	{
        x = (x<<3)+(x<<1)+(c^48);
        c = getchar();
    }
    return x*f;
}

void write(ll x)
{
    if(x>9) write(x/10);
    putchar(x%10+'0');
}

int main()
{
	ll t;
	t = read();
	a[1] = a[2] = 1;
	while(t--)
	{
		ll n = read(),ans = 0;
		for (ll i=1;i<=n;i++)
			ans += solve(fib(i));
		write(ans%9);
		printf("\n");
	}
	return 0;
}

rt，这道题超时咋整