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

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

每行一个数字为答案