
133  The 11th Zhejiang Provincial Collegiate Programming Contest  D
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.
George had enough flowers in N different color, he want quickly calculate the number of beautiful schemes he could use. InputThere 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 <= 10^{18}). OutputFor each test case, output the number of beautiful schemes. Sample Input4 4 5 6 7 Sample Output110075314176 121502550727065600000000 353478234302192141048217600000000 6160946287799856318077344433527848960000 