Given an integer 'K', construct a set 'S' containing all integers from 1 to 2*K-1 (both inclusive). Construct a graph 'G' with vertices represented by all the K-1 element subsets of 'S'. There is an  edge from vertex 'u' to vertex 'v' in 'G', if the corresponding subsets of 'u' and 'v' do not have any element in common. The distance d(u,v) between a vertex 'u' to a vertex 'v' is defined as the shortest path from 'u' to 'v' in 'G'. The diameter of 'G' is defined as the longest distance between any two vertices in 'G'. Output the diameter of the graph and the number of pairs of vertices which have distance equal to the diameter.

Input

The first line of input contains a number 't', the number of test cases.

Each of the following 't' lines contains an integer 'K'.

Output

For each testcase output two space separated integers, the diameter and the number of pairs. Since the numbers can be huge, output all the numbers modulo 1,000,000,007.

Example

Input:

2
2
3

Output:

1 6
2 60

Explanation:

For Case 1:

The graph is a triangle, so  the diameter is 1 and the distance between any 2 pairs of different  vertices is 1. The 6 pairs are: ({1},{2}), ({2},{1}), ({1},{3}),({3},{1}),  ({2},{3}), ({3},{2}).

Constraints:

t <= 25
2 <= K <= 100,000