Valentine's day is coming. (I know, it's still 9 months away, but bear with me) Najib is planning a surprise gift for his wife. Among other gifts and surprises, he will give a bouquet of flowers to her. Since it is a special gift, certain specifications have to met in making the bouquet.
The bouquet will contain N flowers of 4 types. The types of flowers and their specifications are as follows:
Last valentine's day, Najib forgot to wish his wife. He doesn't want to mess up this time. This is why he is starting so early. Now help him by counting the number of ways he can make the bouquet.
The first line will contain a single integer T (1 ≤ T ≤ 105) denoting the number of test cases.
The following T lines will contain a single integer N (0 ≤ N ≤ 1018) denoting the total number of flowers.
For each test case, output a single integer denoting the answer modulo 1018. Print a newline after each output.
There are 7 ways to form a bouquet with 6 flowers: