We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
- Prepare
- Mathematics
- Number Theory
- Number of zero-xor subsets
Number of zero-xor subsets
Number of zero-xor subsets
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 - , , , .