Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Bouquet For My Valentine

By ishtupeed, IamHot · Limits 1s, 512 MB

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 ≤ 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.

Output

For each test case, output a single integer denoting the answer modulo 1018. Print a newline after each output.

Sample

InputOutput
1
6
7

Note:
There are 7 ways to form a bouquet with 6 flowers:

    Discussion

    Statistics


    93% Solution Ratio

    saifkhan007420Earliest, May '18

    Fazlerabbi.Fastest, 0.0s

    dip_BRURLightest, 1.4 MB

    mdvirusShortest, 63B

    Submit

    Login to submit

    Related Contests

    1st AUB Inter University Programming Contest 2018 Ended at 2018-05-12 10:10:00 +0000 UTC
    Replay of 1st AUB Inter University Programming Contest 2018 Ended at 2018-05-15 14:30:00 +0000 UTC