Description

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.

Input

The first line of input contains a number T (1<T<10000), which is the number of test cases. Each of the following T lines contains one integer N (1<N<1000000), which is the number of persons.

Output

For each test case, print a line the number of results of possible exchanging modulo 20090314.

Sample

Input

2
2
4

Output

1
9

Source: Limitfan