Bouquet For My Valentine

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:

• The number of roses must be even.
• The number of tulips must be a multiple of 5.
• There can be at most 4 lilies.
• There can be at most 1 hydrangeas.

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.

Input

The first line will contain a single integer $T$ ($1 ≤ T ≤ 10^5$) denoting the number of test cases. The following $T$ lines will contain a single integer $N$ ($0 ≤ N ≤ 10^{18}$) denoting the total number of flowers.

Output

For each test case, output a single integer denoting the answer modulo $10^{18}$. Print a newline after each output.

Sample

1
6

7