Roundgod is obsessive about linear algebra. Let , everyday she will generate a binary vector randomly in . Now she wonders the probability of generating linearly independent vectors in the next days modulo . Formally, it can be proved that the answer has the form of , where  and  are coprime and  is not a multiple of . The answer modulo thus means , where is the multiplicative inverse of .

Wcy thinks the problem too easy. Let the answer of be , she wants to know , where denotes bitwise exclusive or operation.

The input contains multiple test cases. The first line of input contains one integer , denoting the number of test cases.

In the following  lines, each line contains an integer  describing one test case.

For each test case, output one integer indicating the answer.

3
1
2
3

500000004
194473671
861464136