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!
The first line contains one integer , the number of testcases.
The next lines contain one integer each.
Output lines. Each line is one number, answer to the problem modulo .
For there are sets - and .
For there are sets - , , , .