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.

Loading...

- Practice
- 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 - , , , .