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.
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).
A single line for each test case, containing the answer modulo 314159.
Problem Setter: Md Taha Bin Jawaid (TBJ)