Chayanika loves Mathematics. She is learning a new chapter geometry. While reading the chapter a question came in her mind. Given a convex polygon of n sides. In how many ways she can break it into triangles, by cutting it with (n-3) non-adjacent diagonals and the diagonals do not intersect.

Input

First line of the input will be an integer t (1<=t<=100000) which is the number of test cases. Each test case contains a single integer n (3<=n<=1000) which is the size of the polygon.

Output

For each test case output the no of ways %100007.

Example

Input:
2
3
5

Output:
1
5