Color the necklace

Time Limit: 20000 ms

Memory Limit: 65536 ms

Description

As we all know, girls love necklaces, especially nice necklaces. Recently, huicpc229 has fallen in love with a girl; he wants to bring her a necklace as a gift. Now he has n colors, and the necklace is circular and it has n beads, huicpc229 can use his colors to color the necklace. he wants to know how many different kinds of necklaces he can make,he may not use all the n colors. In this problem, the necklace is same when you rotate it around the center of the necklace or turn it over.

Input

First line is the testcase T. Following T lines, each line is an integer n ( 1≤n ≤ 109 )

Output

Output the answer mod 20090531

Sample Input

4
1
2
3
4

Sample Output

1
3
10
55

Hint

Source

3rd Central South China Programming Contest

提交代码