Having joined forces and preparing for the war with the terminators the humans do know that it will be a tough battle. They plan to strike each base of the terminator and destroy them one by one. A genius computer engineer UD willing to extend his help to his fellow humans found out that each base of the terminator has password protected doors. He was able to recognise the pattern between the passwords. The password is an n character string having even number of zeroes. As you know many strings of this type exist. Help him to 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 <= 10⁶).

Output

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

Example

Input:
2
2
1
Output:
82
9