Bracket Sequences#399
You are given a set of square tiles. Each tile has a bracket symbol printed on it. The tiles can be rotated, so each tile can be used as either an opening bracket or a closing bracket.
Your task is to determine how many different valid bracket sequences can be formed using all the given tiles.
A bracket sequence is considered valid if:
Every opening bracket has a corresponding closing bracket.
The brackets are properly nested.
All tiles are used in the sequence.
The first line contains the integer — the number of test cases. Each of the next lines contains an integer — the number of tiles available for that test case.
Print lines, each containing a single number — the count of different valid bracket sequences that can be formed using all tiles.
Example 1