HZNUOJ

Color the necklace

Tags:
Time Limit:  2 s      Memory Limit:   64 MB
Submission:4     AC:4     Score:99.75

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 makehe 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.

Samples

input
4 1 2 3 4
output
1 3 10 55

Source

3rd Central South China Programming Contest