#include <iostream>
#include <vector>
using namespace std;

typedef long long ll;

const int zero = false;
const int one = true;
const int two = one + true;
const int three = two + true;
const int four = three + true;
const int five = four + true;
const int six = five + true;
const int seven = six + true;
const int eight = seven + true;
const int nine = eight + true;
const int ten = nine + true;

ll product(ll a, ll b) {
	if (b == zero)return zero;
	ll cnt = one;
	ll ret = a;
	while (b >= cnt + cnt) {
		ret += ret;
		cnt += cnt;
	}

	return ret + product(a, b - cnt);
}

ll mod(ll a, ll b) {
	while (a >= b) {
		ll m = b;
		while (a >= m + m)m += m;
		a -= m;
	}
	return a;
}

vector<vector<ll>> mul(vector<vector<ll>>&a, vector<vector<ll>>&b, ll p) {
	vector<vector<ll>>c(a.size(), vector<ll>(b.size()));
	
	for (ll i = zero; i<a.size(); i++) {
		for (ll k = zero; k<b.size(); k++) {
			for (ll j = zero; j<b[zero].size(); j++) {
				c[i][j] = mod((c[i][j] + product(a[i][k],b[k][j])), p);
			}
		}
	}
	return c;
}

vector<vector<ll>> pow(vector<vector<ll>>&a, ll n, ll p) {
	vector<vector<ll>>b(a.size(), vector<ll>(a.size()));
	for (ll i = zero; i<a.size(); i++) {
		b[i][i] = one;
	}
	while (n>zero) {
		if (n & one) b = mul(a, b, p);
		a = mul(a, a, p);
		n >>= one;
	}
	return b;
}

ll fibonacci(ll n, ll p) {
	vector<vector<ll>>a(two, vector<ll>(two));
	a[zero][zero] = one; a[zero][one] = one;
	a[one][zero] = one; a[one][one] = zero;
	a = pow(a, n + one, p);
	return a[one][zero];
}

int main() {
	int T; cin >> T;

	for (int i = zero; i < T; i++) {
		int N; cin >> N;
		
		cout << fibonacci(N-two, product(product(product(product(product(product(product(product(ten,ten),ten),ten),ten),ten),ten),ten),ten) + seven)
			+ fibonacci(N, product(product(product(product(product(product(product(product(ten, ten), ten), ten), ten), ten), ten), ten), ten) + seven) << endl;
	}

	return zero;
}