#include<bits/stdc++.h>
using namespace std;
int a[1001][1001];
int len,n;
void jia(int x){
    for(int i=1;i<=len;i++)a[x][i]=a[x-1][i]+a[x-2][i];
	for(int i=1;i<=len;i++){
		if(a[x][i]>9){
			a[x][i+1]+=a[x][i]/10;
			a[x][i]%=10;
		}
		if(a[x][len+1]>0)len++;
	}
}
int main(){
	int tt;
	cin>>tt;
	while(tt--){
		 memset(a,0,sizeof(a));
		cin>>n;
		len=1;
		a[1][1]=1;
		a[2][1]=1;
		if(n==1)cout<<1<<endl;
		if(n==2)cout<<2<<endl;
		int sum=2;
		for(int i=3;i<=n;i++){
			jia(i);
			for(int j=1;j<=len;j++)sum=(sum+a[i][j])%9;
		}
		cout<<sum%9<<endl;
	}
	return 0;
}