#include <iostream>
#include <string>
#include <vector>
#include <functional>
#define int long long

int z;
int o = !z;
int two = o << o;
int seven = std::minus<int>()(two << two, o);

int MOD;

std::vector<std::vector<int>> a, b;

int suc(int& x) {
	return x = std::plus<int>()(x, o);
}

std::vector<std::vector<int>> mul(std::vector<std::vector<int>> x, std::vector<std::vector<int>> y) {
	std::vector<std::vector<int>> r(x.size(), std::vector<int>(y[z].size(), z));
	for (int i = z; i < x.size(); suc(i)) {
		for (int j = z; j < y[z].size(); suc(j)) {
			for (int k = z; k < x[z].size(); suc(k)) {
				r[i][j] = std::modulus<int>()(std::plus<int>()(r[i][j], std::multiplies<int>()(x[i][k], y[k][j])), MOD);
			}
		}
	}
	return r;
}

void pow_(int p) {
	while (p) {
		if (p & o) a = mul(a, b);
		b = mul(b, b);
		p >>= o;
	}
}

int solve(int n) {
	if (n == o) return o;

	a = std::vector<std::vector<int>>(two, std::vector<int>(two, o));
	a[o][o] = z;
	b = a;

	pow_(std::minus<int>()(n, two));
	return std::modulus<int>()(std::plus<int>()(a[z][z], (a[z][o] << o)), MOD);
}

void init_mod() {
	std::string s;
	s = std::plus<std::string>()(s, std::to_string(o));
	s = std::plus<std::string>()(s, std::to_string(z));
	s = std::plus<std::string>()(s, std::to_string(z));
	s = std::plus<std::string>()(s, std::to_string(z));
	s = std::plus<std::string>()(s, std::to_string(z));
	s = std::plus<std::string>()(s, std::to_string(z));
	s = std::plus<std::string>()(s, std::to_string(z));
	s = std::plus<std::string>()(s, std::to_string(z));
	s = std::plus<std::string>()(s, std::to_string(z));
	s = std::plus<std::string>()(s, std::to_string(seven));
	MOD = std::stoi(s);
}

signed main() {
	init_mod();

	int t;
	std::cin >> t;
	for (int _ = z; _ < t; suc(_)) {
		int n;
		std::cin >> n;
		std::cout << solve(n) << std::endl;
	}

	return z;
}