1799: Color the necklace

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

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

Output the answer mod 20090531

4	
1
2
3
4

1
3
10
55