#include <iostream>
using namespace std;
enum {
	Ca, Cb, Cc, Cd, Ce, Cf, Cg, Ch, Ci, Cj, Ck
};


using ull = unsigned long long;

constexpr ull Adder(ull a, ull b, ull carry) {
	ull ret = Ca;
	for (ull mask = Cb; mask != Ca; mask <<= Cb) {
		ull am = (a & mask);
		ull bm = (b & mask);
		ull rm = am ^ bm ^ carry;
		ret |= rm;
		carry = (am & bm | am & carry | bm & carry) << Cb;
	}
	return ret;
}

constexpr ull Plus(ull a, ull b) {
	return Adder(a, b, Ca);
}

constexpr ull Minus(ull a, ull b) {
	return Adder(a, ~b, Cb);
}

constexpr ull Mul(ull a, ull b) {
	ull ret = Ca;
	for (ull mask = Cb; mask != Ca; mask <<= Cb, a <<= Cb) {
		ull bm = (b & mask);
		if (bm) {
			ret = Plus(ret, a);
		}
	}
	return ret;
}

constexpr ull Pow(ull base, ull exp) {
	if (exp == Ca) return Cb;
	return Mul(base, Pow(base, Minus(exp, Cb)));
}

ull Mod(ull dividend) {
	constexpr ull Modulo = Plus(Pow(Ck, Cj), Ch);
	constexpr ull Shift = Minus(Pow(Cg, Cc), Cc);
	for (ull divisor = Modulo << Shift; divisor >= Modulo; divisor >>= Cb) {
		if (dividend >= divisor) {
			dividend = Minus(dividend, divisor);
		}
	}
	return dividend;
}

struct Hoge {
	ull k;
	ull l;
};

Hoge FormHoge(ull i) {
	if (i == Ca) return Hoge{ Cb, Ca };
	if (i == Cb) return Hoge{ Ca, Cb };
	ull half = i >> Cb;
	if ((half << Cb) != i) {
		Hoge sub = FormHoge(Minus(i, Cb));
		return Hoge{ sub.l, Mod(Plus(sub.k, sub.l)) };
	}

	Hoge tmp = FormHoge(half);
	ull new_k = Mod(Plus(Mul(tmp.k, tmp.k), Mul(tmp.l, tmp.l)));
	ull new_l = Mod(Mul(tmp.l, Plus(tmp.k << Cb, tmp.l)));
	return Hoge{ new_k, new_l };
}

ull Lucas(ull i) {
	Hoge hoge = FormHoge(i);
	return Mod(Plus(hoge.k << Cb, hoge.l));
}

int main() {
	ull T;
	cin >> T;
	for (ull i = Ca; i < T; i = Plus(i, Cb)) {
		ull a;
		cin >> a;
		cout << Lucas(a) << endl;
	}
	return Ca;
}