Maximum Non-Crossing Handshakes

In this problem, you are given a number of employees arranged in a circle. Your task is to compute the maximum number of non-crossing handshakes among them. A handshake is drawn as a chord between two people and no two chords are allowed to cross.

This problem is equivalent to computing a Catalan number. Specifically, if there are N employees (where N is even), the maximum number of non-crossing handshakes is given by the \(\frac{N}{2}\)th Catalan number. The Catalan numbers \(C_n\) are defined by the recurrence:

\(C_0 = 1, \quad C_n = \sum_{i=0}^{n-1} C_i \cdot C_{n-1-i}\)

Note: You may assume that the input number N is always even. If not, your program should handle it appropriately.

inputFormat

The input is given via standard input (stdin) with the following format:

• The first line contains an integer T, the number of test cases.
• Each of the next T lines contains a single even integer N, representing the number of employees.

outputFormat

For each test case, output the maximum number of non-crossing handshakes on a separate line to standard output (stdout).

3
4
6
8

2
5
14