DCEPC801 - Family Problem

no tags 

Shima has a very unhappy family. His family members always remain sad for one or the other problems and they are so addicted to this nature that they cannot live a second without being sad. So to ensure that they never become happy, every day they take all the problems they had in the last 7 days and think about all of them and remain sad for the whole day.

For example: Let’s say they had p1 problems yesterday, p2 problems day before yesterday and so on, then today they will think about all the problems occurred in the last 7 days and remain sad and so problems for today are total problems (i.e. the summation) that occurred in the last 7 days.

Well sad story isn’t it!? But they were not like this always. It all started when Shima was born on the Day no. 7 (yes it was the first problem for this strange family). They had no problems from Day no. 0 to Day no. 6 and they had only single problem on the day Shima was born.

Can you predict how many problems they will think about on the Day no. n?? Output it modulo 86399.

Input

First line contains an integer T, the no. of test cases.

Next T lines contain one integer per line, n.

Output

Output T lines, each corresponding to T test cases, containing one integer per line, the problems Shima’s family think about on Day no. n.

Contraints

1<=n<=1000000000

1<=T<=20

 

Example

Input:
3
1
10
12

Output:
0
4
16

hide comments
nadstratosfer: 2020-07-17 22:30:16

Some testfiles are broken, attempting to read T cases results in crash while reading till EOF gives WA.

dce coders: 2012-08-20 18:12:24

it was mistakenly moved to classic.. moved to tutorial now :)

Ehor Nechiporenko: 2012-08-20 16:34:06

There are very many such problems last time


Added by:dce coders
Date:2012-08-19
Time limit:2s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:ASM32-GCC MAWK BC C-CLANG C C++ 4.3.2 CPP CPP14 CPP14-CLANG COBOL COFFEE D-CLANG D-DMD DART ELIXIR FANTOM FORTH GOSU GRV JAVA JS-MONKEY KTLN NIM NODEJS OBJC OBJC-CLANG OCT PICO PROLOG PYPY PY_NBC R RACKET RUST CHICKEN SQLITE SWIFT UNLAMBDA VB.NET
Resource:Own Problem