import java.io.PrintWriter;
import java.math.BigInteger;
import java.util.Arrays;
import java.util.Scanner;

public class Main {
	void solveTestcase(final Scanner in, final PrintWriter out) {
		long n = in.nextLong();
		out.println(fib(n, mod));
	}
	
	static int zero;
	static int one;
	static BigInteger mod;
	static {
		one = Math.abs(~zero);
		mod = BigInteger.TEN.pow(BigInteger.TEN.subtract(BigInteger.ONE).intValue());
		mod = mod.add(BigInteger.TEN).subtract(BigInteger.ONE).subtract(BigInteger.ONE).subtract(BigInteger.ONE);
	}
	void solve() {
		try (final PrintWriter out = new PrintWriter(System.out)) {
			try (final Scanner in = new Scanner(System.in)) {
				int t = in.nextInt();
				while (t > zero) {
					t = dec(t);
					solveTestcase(in, out);
				}
			}
		}
	}

	public static void main(String[] args) {
		new Main().solve();
	}

	static BigInteger[][] mulmat(BigInteger[][] a, BigInteger[][] b, BigInteger mod) {
		final int n = a.length;
		final int v = b.length;
		final int m = b[zero].length;
		
		BigInteger[][] res = new BigInteger[n][m];
		for(int i = zero; i < n; i = inc(i))
			for(int j = zero; j < m; j = inc(j))
				res[i][j] = BigInteger.ZERO;
		for(int i = zero; i < n; i = inc(i))
			for(int k = zero; k < v; k = inc(k)) {
				final BigInteger aa = a[i][k];
				for(int j = zero; j < m; j = inc(j)) {
					res[i][j] = res[i][j].add(aa.multiply(b[k][j]));
				}
			}
		for(int i = zero; i < n; i = inc(i))
			for(int j = zero; j < m; j = inc(j))
				res[i][j] = res[i][j].mod(mod);
		
		return res;
	}
	
	static int inc(int x) {
		return BigInteger.valueOf(x).add(BigInteger.ONE).intValue();
	}
	
	static int dec(int x) {
		return BigInteger.valueOf(x).subtract(BigInteger.ONE).intValue();
	}
	
	static BigInteger[][] powmat(long r, BigInteger mod, BigInteger[][] mat) {
		final int n = mat.length;
		BigInteger[][] x = new BigInteger[n][n];
		for(int i = zero; i < n; i = inc(i)) {
			for (int j = zero; j < n; j = inc(j)) {
				x[i][j] = BigInteger.ZERO;
			}
		}
		for(int i = zero; i < n;  i = inc(i)) {
			x[i][i] = BigInteger.ONE;
		}
		
		for(;r > zero; r >>>= BigInteger.ONE.intValue()) {
			if((r&one) == one) {
				x = mulmat(x, mat, mod);
			}
			mat = mulmat(mat, mat, mod);
		}

		return x;
	}
	
	static BigInteger fib(long n, BigInteger mod) {
		BigInteger[][] mat = new BigInteger[][]{
			new BigInteger[]{BigInteger.ONE, BigInteger.ONE,},
			new BigInteger[]{BigInteger.ONE, BigInteger.ZERO,},
		};
		BigInteger[][] matmat = new BigInteger[][]{
			new BigInteger[]{BigInteger.ONE,},
			new BigInteger[]{BigInteger.valueOf(inc(one)),},
		};
		return mulmat(powmat(n, mod, mat), matmat, mod)[one][zero];
	}
	
	static void dump(Object...objects) { System.err.println(Arrays.deepToString(objects)); }
}