小y很喜欢跟位运算有关的问题，这天，他想让你解决一个奇怪的问题：给定一个正整数n，求出 （2 * 1）⊕（2 * 2）⊕ ...... ⊕（2 * n）的结果。
由于答案可能很大，请对1e9+7取模。小y为了让你能更轻松地解决这个问题，他保证n一定是4的倍数。

注意，⊕为异或运算。

第一行一个正整数T代表测试数据数，随后T行每行给定一个正整数n，对于每个n请打印上述问题的答案并换行

T ≤ 10⁵，n ≤ 10¹⁸

输出共有n行，每个输出占1行，行尾无空格。