Bob is playing with binary strings. He defines two strings and to be similar if at least one of the following conditions holds:
- The lengths of both and must be divisible by . Let denote the first half of , and denote the second half. Similarly, define and as the first and second halves of . Then and are similar if either:
- is similar to and is similar to or
- is similar to and is similar to
If both conditions do not hold then and are not similar.
Bob begins to wonder about particular lengths of binary strings. These lengths are .
For each , Bob generates all possible binary strings of length . He wonders how many ordered pairs of binary strings from his set are similar. Since these numbers may be massive, print the answers modulo .
Constraints
In all subtasks,
Subtask 1 [5%]
Subtask 2 [10%]
All the are odd integers.
Subtask 3 [15%]
Subtask 4 [10%]
Subtask 5 [30%]
Subtask 6 [30%]
Input Specification
The first line contains a single integer, .
lines follow, the -th of which containing a single integer, .
Output Specification
Output lines, the -th of which containing the answer modulo for binary strings of length .
Sample Input 1
1
2
Sample Output 1
6
Sample Input 2
2
3
4
Sample Output 2
8
54
Explanation for Sample Output 2
There are a total of ordered pairs of similar strings for binary strings of length , and there are a total of ordered pairs of similar strings for binary strings of length .
Comments