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