#描述#
There are N persons gathering together each with a unique gift. They are going to have an exchange of their gifts, satisfying the condition that everyone gets a new gift when the gathering is over. You are to calculate the number of possible results of exchanging.

#格式#
##输入格式##
The first line of input contains a number T (1&ltT&lt10000), which is the number of test cases. Each of the following T lines contains one integer N (1&ltN&lt1000000), which is the number of persons.

##输出格式##
For each test case, print a line the number of results of possible exchanging modulo 20090314.

#样例1#
##样例输入1##

2
2
4

##样例输出1##

1
9

#限制#
1000ms
32768KB

#提示#

#来源#
Limitfan