Скобочные последовательности#399
Вам даны квадратные плитки. На каждой плитке изображён символ круглой скобки. Плитки можно поворачивать, поэтому каждую плитку можно использовать как открывающую или как закрывающую скобку.
Ваша задача — определить, сколько различных правильных скобочных последовательностей можно составить, используя все данные плитки.
Скобочная последовательность считается правильной, если:
Каждой открывающей скобке соответствует закрывающая скобка.
Скобки правильно вложены.
Все плитки использованы в последовательности.
В первой строке задано число — количество тестов. В каждой из следующих строк задано по одному числу — количество доступных плиток для данного теста.
Выведите строк, каждая из которых содержит одно число — количество различных правильных скобочных последовательностей, которые можно составить из всех плиток.
Example 1