Luke Skywalker successfully leads the rebel starship fleet to break the Emperor's siege of the planet Endor. The rebels, jubilant in their victory, return to their base on the moon of Endor to pay their homage to Princess Leia. They fly towards the parking bay where there are n parking slots in a row. One by one n starships numbered S₁ to S_n enter the parking bay. Each rebel R_i heads to his favorite parking slot P_i, and if it is free, he docks his starship there. Otherwise, he continues further to the next free slot and occupies it. But if all succeeding slots are occupied, he leaves for good. How many sequences P_i are such that every rebel can dock his starship?

Input Description

The first line of the input is a positive integer t ≤ 20, which is the number of test cases. The descriptions of the test cases follow one after the other. The description of each test case contains exactly one line (a positive integer), containing the value of n ≤ 1000000.

Output Description

The output consists of exactly t lines. The ith line should be A_i%10007, where A_i is the number of sequences in the i^th case, and 'x%y' represents the remainder when x is divided by y.

Example

Input

2
1
2

Output
1
3

Explanation: In the given example, 11, 12 and 21 are the possible sequences.