You are given an integer . Consider set . How many subsets with ( denotes xor operation) are there?
Print your answer modulo .
Note that the xorsum of an empty set is zero!

Input Format
The first line contains one integer , the number of testcases.
The next lines contain one integer each.

Output Format
Output lines. Each line is one number, answer to the problem modulo .

Constraints

Sample Input

2
1
2

Sample Output

2
4

Explanation
For there are sets - and .
For there are sets - , , , .