All Submissions


Problem Statement

As you all are aware 2013 began on a rather disappointing note for our institute with the Elployees' Association going on an indefinite strike against the college administration. After weeks of indecisiveness the matter was finally resolved and the employees' were promised a hike in their salaries which was to be implemented within 15 days.
However more than 20 days passed and none of the promises made by the administartion were fulfuilled. So while the whole college was busy attending the Inaugration ceremony of the Anunual Athletics meet on Friday, one discontent Employee went and electronically locked all the doors of the Main Building. The Board of Directors is suppose to make a visit to the college on Monday. The administartion panicked and asked for ACM to help them decipher the code to unlock the doors before Monday.
We found out that each door of the main building has a password and we also recognised the pattern between the passwords. The password is an n character string having even number of zeroes. We want you to take up some of our responsibility as future members of ACM. As you know many strings of the above said type exist. Help us find out the total number of such strings. Each character in the password string is a digit from 0 to 9.



Input

The first line of input contains an integer t<=50, the number of test cases. Then t test cases follow each containing a line with a single integer n (1<=n<=106).

Output

A single line for each test case, containing the answer modulo 314159.

Sample Input


2
2
1


Sample Output


82
9


Problem Setter: Md Taha Bin Jawaid (TBJ)

Languages: C,C++,C#,Java,JavaScript,Pascal,Perl,PHP,Python,Ruby

Time Limit: 1 Second(s)
Score: 100 Point(s)
Input File Limit: 50000 Bytes

Submit

Login to post clarification.

No Clarifications.

Contest

Mode Judge

Passive

Online

Overall Rankings

RankNameScore
1xyz0
2Ams0
3TIP0
4team420
5xyzz0
6asdasdasd0
7abcd0
8khankhan0
9Gabriel0
10gigel0