Watson gives a square of side length 1 to Sherlock. Now, after each second, each square of some arbitrary side will break into four squares each of side (as shown in the image below).

Now, Watson asks Sherlock: What will be the sum of length of solid lines after seconds?

As the number can be large print result mod .

For example, after 0 seconds, the length is 4.
After 1 second, the length is 6.

Input Format
First line contains , the number of testcases. Each testcase contains in one line.

Output Format

For each testcase, print the required answer in a new line.

Constraints

Sample input

3
0
1
5

Sample output

4
6
66