<|instruction|>
Solve the below problem. The solution should start with an abridged problem statement. Then key observations. Then full solution based on the observations. Then C++ and Python implementations with comments.

247. Difficult Choice
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).

Input
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
Output N lines (one line per test) with requested numbers.

Sample test(s)

Input
2
3
5

Output
8
52

<|response|>
## 1) Abridged problem statement (concise)

For each test case, given an odd prime \(P\) \((1<P<1000)\), consider numbers \(1,2,\dots,2P\). Count how many ways to choose **exactly \(P\) distinct numbers** such that their sum is divisible by \(P\). Output the count for each test.

---

## 2) Key observations needed to solve the problem

1. **Two obvious valid subsets exist**
   - \(A=\{1,2,\dots,P\}\) and \(B=\{P+1,P+2,\dots,2P\}\) both have size \(P\).
   - \(\sum_{i=1}^P i=\frac{P(P+1)}{2}\) is divisible by \(P\), so \(A\) is valid.
   - \(\sum_{i=P+1}^{2P} i\) is also divisible by \(P\), so \(B\) is valid.
   - So we already have **2** good subsets.

2. **All other \(P\)-subsets can be partitioned into groups of size \(P\)**
   - For any other subset \(S\) (not \(A\) or \(B\)), let
     \[
     k = |S \cap \{1,\dots,P\}|
     \]
     Then \(1 \le k \le P-1\).

3. **Cyclic shift trick**
   - “Shift” only the elements of \(S\) that lie in \(\{1,\dots,P\}\) by \(i\) modulo \(P\), for \(i=0,1,\dots,P-1\).
   - This creates exactly \(P\) distinct subsets \(S_0,S_1,\dots,S_{P-1}\) (an orbit).

4. **Exactly one subset per group has sum divisible by \(P\)**
   - Shifting increases the total sum by \(k\cdot i \pmod P\).
   - Since \(P\) is prime and \(1\le k\le P-1\), \(\gcd(k,P)=1\), so \(k i \bmod P\) runs through all residues exactly once.
   - Hence among the \(P\) sums, exactly **one** is \(0 \bmod P\).

---

## 3) Full solution approach

Let total number of \(P\)-subsets be:
\[
\binom{2P}{P}.
\]

- Two of these subsets are special: \(A\) and \(B\), both good.
- The remaining \(\binom{2P}{P}-2\) subsets are partitioned into disjoint groups (orbits) of size \(P\).
- Each such group contributes exactly 1 good subset.

Therefore, total good subsets:
\[
\boxed{\;2 + \frac{\binom{2P}{P}-2}{P}\;}
\]

### Computation
- For \(P\) up to 999, \(\binom{2P}{P}\) is enormous, so we need big integers.
- Compute \(\binom{2P}{P}\) using the multiplicative exact formula:
\[
\binom{2P}{P}=\prod_{i=0}^{P-1}\frac{2P-i}{i+1}
\]
Perform multiplication then exact division at each step.

Finally compute:
\[
\text{ans} = 2 + \frac{C-2}{P}.
\]

Time per test is \(O(P)\) big-integer operations, fine for \(P<1000\).

---

## 4) C++ implementation with detailed comments

```cpp
#include <bits/stdc++.h>
#include <boost/multiprecision/cpp_int.hpp>
using namespace std;
using boost::multiprecision::cpp_int;

/*
  We use boost::multiprecision::cpp_int for arbitrary precision integers.
  This avoids writing a custom BigInteger and is fast enough for P < 1000.
*/

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    while (T--) {
        int P;
        cin >> P;

        // Compute C = C(2P, P) using multiplicative formula:
        // C(2P,P) = Π_{i=0..P-1} (2P - i) / (i + 1)
        // Division is exact at every step.
        cpp_int C = 1;
        for (int i = 0; i < P; ++i) {
            C *= (2 * P - i);
            C /= (i + 1);
        }

        // Apply derived formula:
        // answer = 2 + (C(2P,P) - 2) / P
        cpp_int ans = 2 + (C - 2) / P;

        cout << ans << "\n";
    }
    return 0;
}
```

---

## 5) Python implementation with detailed comments

```python
import sys

def solve():
    data = sys.stdin.read().strip().split()
    if not data:
        return
    t = int(data[0])
    idx = 1
    out = []

    for _ in range(t):
        p = int(data[idx]); idx += 1

        # Compute C(2p, p) exactly using multiplicative formula.
        # Python integers are arbitrary precision.
        c = 1
        for i in range(p):
            c *= (2 * p - i)
            c //= (i + 1)   # exact division

        # Apply the proven counting formula:
        # ans = 2 + (c - 2) / p
        ans = 2 + (c - 2) // p
        out.append(str(ans))

    sys.stdout.write("\n".join(out))

if __name__ == "__main__":
    solve()
```

These implementations directly encode the math result:
\[
\boxed{\text{answer} = 2 + \frac{\binom{2P}{P}-2}{P}}
\]
and handle the large values via big integers.