Welcome to ZOJ
133 - The 11th Zhejiang Provincial Collegiate Programming Contest - D
Chessboard and Flowers

Time Limit: 10 Seconds      Memory Limit: 131072 KB

As is known to all, a chessboard has 8 rows and 8 columns, as shown in the following diagram, in which a '-' represents a light square and a '#' represents a dark square.

- # - # - # - #
# - # - # - # -
- # - # - # - #
# - # - # - # -
- # - # - # - #
# - # - # - # -
- # - # - # - #
# - # - # - # -

George is very good at both maths and chess. He also loves life and flowers. In a sunny afternoon, he picked up a lot of flowers in full bloom. To decorate his chessboard, he decided to place a flower on each cell of the chessboard. Two flowers placed in different type of cells (light and dark) will look different, even they have petals of same color. By the way, two flowers with petals of different colors will always look different.

After a variety of different decorating schemes were tried, George found some schemes were very boring and ugly, while others were interesting and beautiful. A decorating scheme is regarded as beautiful if every flower in the same row look different pairwise and every flower in the same column also look different pairwise.

We can use letters to represent flowers of different colors. For example, 'A' and 'a' represent red flowers; 'B' and 'b' represent blue flowers. A lowercase letter represents a flower in a dark cell and an uppercase letter represents a flower in a light cell. The following table is a beautiful scheme when George had 4 types of flowers.

A a B d C c D b
a A d C b D c B
B b C a D d A c
b B a A c C d D
C c D b A a B d
c C b D d B a A
D d A c B b C a
d D c B a A b C

George had enough flowers in N different color, he want quickly calculate the number of beautiful schemes he could use.


There are multiple test cases. The first line of input contains an integer T (about 10000) indicating the number of test cases. For each test case:

There is one integer N (4 <= N <= 1018).


For each test case, output the number of beautiful schemes.

Sample Input


Sample Output


Submit    Status