No tags yet

No tag edit access

time limit per test: 0.25 sec.

memory limit per test: 65536 KB

memory limit per test: 65536 KB

input: standard

output: 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).

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

3

5

Output

8

52

52

Author: | Alexey Preobrajensky |

Resource: | Petrozavodsk Summer Training Sessions 2004 |

Date: | August 25, 2004 |

Codeforces (c) Copyright 2010-2019 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Oct/17/2019 22:40:08 (e1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|