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 ≤ 109 ).
Output the answer mod 20090531.