In People's Republic Of Running, people are crazy about runnning. They keep a habit of running everyday, especially the Head King, because he isn't confident about his figure (please don't tell him~).

The Head King is going to build a new city, which contains N towns. He want to build some bidirectional roads between some of the towns (each road connect two towns) and choose some of them to form his private running route. The Head King can't accept more than one bidirectional roads between two towns, because he has no sense of direction and it will make him bemused. He prefers enjoying the landscape changing while running, so he can't stand any same road on his running route.

Now, the Head King wants to know the total number of scheme of road constructing. Every scheme satisfies that there exist a town for him both to start and finish running(the running route contains at least one road). Please note the towns in the city needn't to be connected to each other

First line contains T(T <= 10), the number of test cases.

For each case, there is one single line containing one non-negative integer N(n <= 2e5).

It is guarantee that there are at most one case in which n >= 1000

For each test case, output a single number —— the number of schemes modulo the population of King's country(1004535809).

In sample 1, the Head King can't design any scheme.

In sample 2, the Head King can build three roads:1-2, 2-3, 3-1, and he can start from town 1 (2 and 3 are also legal) and run along the route:1-2-3-1 (or 1-3-2-1).

In sample 3, one possible scheme is building 3 roads:1-3, 3-4, 4-1, and the Head King can start from town 3 and run along the route:3-1-4-3.

在一个名叫People's Republic Of Running的国度，大家都喜欢跑步。他们天天跑步，特 别是Head 国王，因为他对自己的身材不够自信（请不要告诉他）。
现在，Head国王打算建造一个新的城市作为新的都城，新都城包含了 个县城。然后 国王要在 个县城之间修建能够跑步的无向道路，然后选取其中的一些作为自己的跑步 路线。国王不希望两个县城之间有多余一条无向道路，因为国王是个路痴，这样会使 他困惑。因为国王跑步的时候希望沿途的风景时刻不同，所以他不能够接受他在跑步 的时候经过相同的道路。
国王现在向所有的人征集道路修建的方案数，使得他能够从至少一个县城出发，经过 他自己确定的跑步路线（至少需要包含一条道路）后回来。都市中的县城不必联通。
输入： 组数据（ ），接下来 行，每行一个数字 。保证 至多只有一组数据大于1000。 输出：国王要求的方案数，对国家人口数（ ）取模。
样例输入 3 2 3 4
样例输出 0 1 33