#include<iostream>
#include<algorithm>
#include<map> 

using namespace std;
	
int fib[1000001] = { 0, 1, 1 }, ans[1000001];
pair<int, int >n[1000001];

bool cmp( pair<int, int >a, pair<int, int >b ) {
	
	return a.first < b.first;
	
}

int main( ) {
	
	int t, last = 2, sum = 2; cin >> t;
	for ( int i = 1; i <= t; i++ )
		cin >> n[i].first, n[i].second = i;
		
	sort( n + 1, n + t + 1, cmp );
	
	for ( int x = 1; x <= t; x++ ) {
		int nn = n[x].first;
		
		for ( int i = last + 1; i <= nn; i++ )
			fib[i] = fib[i-1] + fib[i-2], fib[i] %= 9, sum += fib[i], sum %= 9;
			
		ans[n[x].second] = sum;
		
		last = nn;
	}
	
	for ( int i = 1; i <= t; i++ )
		cout << ans[i] << endl;
	
	return 0;
	
}