DCEPC801 - Family Problem

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 number 7 (yes it was the first problem for this strange family). They had no problems from day number 0 to day number 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 number n? Output it modulo 86399.

Input

First line contains an integer T, the number 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 number n.

Constraints

1 ≤ n ≤ 1000000000

1 ≤ T ≤ 20

Example

Input:
3
1
10
12

Output:
0
4
16

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 NCSHARP C++ 4.3.2 CPP CPP14 CPP14-CLANG COBOL COFFEE D-CLANG D-DMD DART ELIXIR FANTOM FORTH GOSU GRV JAVA JS-MONKEY JULIA KTLN NIM NODEJS OBJC OBJC-CLANG OCT PICO PROLOG PYPY PYPY3 PY_NBC R RACKET RUST CHICKEN SQLITE SWIFT UNLAMBDA VB.NET
Resource:Own Problem

hide comments
2020-07-17 22:30:16
Some testfiles are broken, attempting to read T cases results in crash while reading till EOF gives WA.
2012-08-20 18:12:24 dce coders
it was mistakenly moved to classic.. moved to tutorial now :)
2012-08-20 16:34:06 Ehor Nechiporenko
There are very many such problems last time
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.