有一个由所有长度为 的合法括号（括号序列中只含有 ( 和 )）序列组成的 Trie 树，问在该树上最多可以选取多少条边，使得任意两条边之间都没有公共端点。
(
)
因为答案可能很大，所以你只需要输出其对 取模后的结果即可。
本题有多组数据。
第一行一个整数 表示共有 组数据。
对于每组数据：
一行一个整数表示答案。
5 1 2 4 6 9
1 3 27 270 10350
对于 的分数满足 。
对于全部的分数满足 。
