SP24979 LOVEBIRDS - She was in Love with BST

Devo又一次和男友分手了！[皱眉](../../gfx/jscripts/tiny_mce/plugins/emotions/img/smiley-frown.gif "皱眉") 在他们经历了一连串分分合合之后，她终于决定彻底结束这段感情。 为了让自己不去多想感情的事，她开始钻研自己最爱的动态规划。在过程中，她遇到了一个让人抓狂的问题： 给定一个整数 $N$，要求计算所有在集合 $\{1, 2, \ldots, N\}$ 的不同排列上构建的结构上唯一的二叉搜索树的总数。 如果一棵二叉搜索树的中序遍历与某个排列相同，则称该树是基于这个排列构建的。 如果两个排列在某位置 $i$ 处的元素不同，则称这两个排列不同。 她被这个问题弄得很苦恼，希望你能帮她解决这个难题！ **注意**：这个结果可能非常大，因此需要对结果取模 $1908$。 此外，她指出，二叉搜索树的中序遍历是唯一确定的。 想了解更多有关二叉搜索树的知识，请查看 [维基百科](https://en.wikipedia.org/wiki/Binary_search_tree)。

第一行输入一个整数 $T$，表示测试用例的数量。 接下来 $T$ 行中，每行输入一个整数 $N$。 （$N$ 和 $T$ 的最大值均为 $1000$）

对于每个测试用例，输出一个整数，表示计算结果对 $1908$ 取模后的值。

$$1 \le T \le 1000$$ $$1 \le N \le 1000$$ **本翻译由 AI 自动生成**