？？

#include<bits/stdc++.h>
using namespace std;
int fib[1000005];
void fib_(){
	fib[1]=1;
	for(int i=2;i<=1000005;i++){
		fib[i]=fib[i-1]+fib[i-2];
	}
}
int s(int x){
	int ans=0;
	while(x>=10){
		ans+=x%10;
		x/=10;
	}
	ans+=x;
	return ans;
}
int main() {
	fib_();
	int t;
	cin>>t;
	for(int i=1;i<=t;i++){
		int n;
		cin>>n;
		int ans=0;
		for(int j=1;j<=n;j++){
			ans+=s(fib[j]);
		}
		cout<<ans%9<<endl;
	}
	return 0;
}