Problem B. Spanning Trees

Time limit: 5 seconds


One of the very sad news during this summer was that we lost the Candlenut Tree located between the Main Library and Knowles Building. The tree had witnessed the vicissitudes in its environs and accompanied us for about four decades!

To commemorate this tree, let's now do a problem in spanning trees.

Let Kn denote the complete undirected graph with n vertices. (i.e., Kn is a graph with n different vertices where every two vertices are connected.) Then you have two tasks:

  1. Find the maximum possible number of spanning trees of Kn such that any two of them have no common edges.
  2. Find the total number of all possible spanning trees of Kn.


The first line contains an integer, specifying the number of test cases. There will be at most 5000 cases.
For each test case, there will be one line with an integer n (2 ≤ n ≤ 5000), representing the number of vertices.


Each case should have one line of output, containing two numbers with one space in between (i.e., "X Y").
The first number X is the maximum possible number of edge-disjoint spanning trees modulo 10007.
The second number Y is the total number of all possible spanning trees modulo 10007.

Sample Input


Sample Output

1 1
1 3
2 16


Michael Chen