SP7886 ADV04I1 - Boards (Hard)

Super Board Games Inc. 是一家大型棋盘游戏制造公司。最近，他们设计了一款新游戏，有望在市场上大受欢迎。这款游戏需要一个由正方形格子组成的棋盘。棋盘的左侧边和底边必须是平整的，并且从左到右每列格子的高度不能递增。此外，棋盘必须能够用多米诺骨牌完全覆盖。经过实验，人们发现当棋盘由 $n$ 个格子组成时，游戏体验最佳。因此，公司希望发布尽可能多的不同版本的游戏，每个版本使用不同的 $n$ 格棋盘。请帮忙计算有多少种不同的棋盘可以用于发布。

第一行包含整数 $T$，表示测试用例的数量。接下来的每一行包含一个整数 $n$，表示棋盘上的格子数量。

对于每个测试用例，请输出题目所求的答案。

$$1 \le T \le 10^5, \quad 1 \le n \le 10^5$$ **本翻译由 AI 自动生成**