Problem B. Spanning Trees

Problem

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 K_n denote the complete undirected graph with n vertices. (i.e., K_n 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 K_n such that any two of them have no common edges.
2. Find the total number of all possible spanning trees of K_n.

Input

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.

Output

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

3
2
3
4

Sample Output

1 1
1 3
2 16

Author