2019.10.20 is the 110th birthday of HPU. On that day, you can see the string "110" everywhere.
Hery is given an integer n in decimal, he can transform n to a **binary string** S. For example: , so 6 can be transformed to "110". But hery thinks S is too short, so he constructs n's **birthday string** T by repeating n's **binary string** S for n times. So for n=6, n's **birthday string** T is:

"110110110110110110"

For n's **birthday string** T, hery wants you to calculate how many pairs (i,j,k) satisfy and .

The first line is an integer t, the number of test cases.
Next t lines, for each line, there is an integer n.

For each n, output the answer mod .

4
1
2
3
11

0
1
0
1815