use std::io::{stdout, BufWriter, Read, Write};
use std::ops::{Mul, Div, Rem};

fn main() {
	let mut input = String::new();
	std::io::stdin().read_to_string(&mut input).unwrap();
	let mut newline = String::new();
	newline.push(input.pop().unwrap());
	let mut input = Box::leak(input.into_boxed_str()).split_ascii_whitespace();
	let mut out = BufWriter::new(Box::leak(Box::new(stdout())).lock());
	let t: usize = input.next().unwrap().parse().unwrap();
	let zero = t - t;
	for _ in zero..t {
		let n: isize = input.next().unwrap().parse().unwrap();
		out.write_all(solve(n).to_string().as_bytes()).unwrap();
		out.write_all(newline.as_bytes()).unwrap();
	}
}

fn solve(mut n: isize) -> isize {
	let one = n.div(n);
	let zero = one - one;
	let two = one + one;
	let four = two + two;
	let seven = one | two | four;
	let sfs = seven << four | seven;
	let mut modulo = sfs << (two + seven) | sfs;
	modulo ^= seven << two;
	modulo = modulo << (four + one) ^ seven ^ two;
	modulo = modulo << (seven + two) | seven;
	let mut m = vec![vec![one, one], vec![one, zero]];
	let mut res = vec![vec![one, zero], vec![zero, one]];
	n -= one;
	while n > zero {
		if n & one == one {
			res = mat_mult(&res, &m, modulo);
		}
		m = mat_mult(&m, &m, modulo);
		n >>= one;
	}
	let ans = (res[zero as usize][zero as usize] + res[zero as usize][one as usize].mul(two).rem(modulo)).rem(modulo);
	ans
}

pub fn mat_mult(a: &[Vec<isize>], b: &[Vec<isize>], modulo: isize) -> Vec<Vec<isize>> {
	let n = a.len();
	let one = n.div(n);
	let zero = one - one;
	let m = a[zero].len();
	assert_eq!(b.len(), m);
	let o = b[zero].len();
	let mut res = vec![vec![zero as isize; o]; n];
	for i in zero..n {
		for j in zero..m {
			for k in zero..o {
				res[i][k] = (res[i][k] + a[i][j].mul(b[j][k])).rem(modulo);
			}
		}
	}
	res
}