As we all know, girls love necklaces, especiallynice necklaces. Recently, huicpc229 has fallen in love with a girl; he wants tobring her a necklace as a gift. Now he has n colors, and the necklace is circular and it hasn beads, huicpc229 can use his colors to color the necklace. he wants to knowhow many different kinds of necklaces he can make，he may not use all the n colors. In this problem, the necklace issame when you rotate it around the center of the necklace or turn it over.
Colorthenecklace
Input
First line is the testcase T.
Following T lines, each line is an integer n ( 1≤n ≤ 10^9 )
Following T lines, each line is an integer n ( 1≤n ≤ 10^9 )
Output
Output the answer mod 20090531
Sample Input
4
1
2
3
4
Sample Output
</p>1
3
10
55