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