time limit per test: 0.25 sec.
memory limit per test: 65536 KB

input: standard
output: standard

In a bowling club "Odd Prime Ball" 2P colored bowling balls numbered from 1 to 2P are available for the game, where P is an odd prime number.
Antony noticed that he has a good fortune if he correctly chooses balls for the game. He thinks that his choice is correct if the sum of numbers of chosen balls is divisible by P. Moreover, the number of balls Antony choses must be equal to P, otherwise he will gain no fortune and lose the game. So he needs to choose P different balls for the game.
He wants to know how many ways he can choose the balls for the game to have a good fortune.
In the first example from balls with weights (1, 2, 3, 4, 5, 6) Antony can choose the following 8 combinations: (1, 2, 3); (1, 2, 6); (1, 3, 5); (1, 5, 6); (2, 3, 4); (2, 4, 6); (3, 4, 5); (4, 5, 6).

The first line of input contains single integer N the number of tests (0<=N<=100). The following N lines contain tests descriptions (one line per test). Each test description consists of a single odd prime number P (1<P<1000).

Output N lines (one line per test) with requested numbers.

Input

2
3
5