Guardian is very weak at maths but still to compete in a certain exam he has to get good grades in mathematics this time. In the first class of the semester the Prof. asked students to find the number of ways deck (having N cards) could be shuffled that exactly one card is at the same position as before, and the students who successfully do this will be awarded with good marks in mid terms. Help Guardian solve this problem.

Input

First line contains an integer T, the number of test cases (T <= 10000). Then following T lines contain an integer N (N <= 1000000) the number of cards in the deck.

Output

For each test case you have to output the number of ways possible meeting the Prof's requirements modulo 10000009.

Example

Input:
1
3

Output:
3

Let's say the initial deck configuration was {1, 2, 3}, then 3 possible shufflings are {1, 3, 2}, {2, 1, 3}, {3, 2, 1}