题号：NC50748
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 32 M，其他语言64 M
64bit IO Format: %lld
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 32 M，其他语言64 M
64bit IO Format: %lld
题目描述
ITX351要铺一条
的路，为此他购买了N块
的方砖。可是其中一块砖在运送的过程中从中间裂开了，变成了两块
的砖块！
ITX351由此产生了一个邪恶的想法：他想要在这条路上故意把两块的砖块分开铺，不让两块砖有相邻的边，其他砖块可以随意铺，直到整条路铺满。这样一定可以逼死自身强迫症sea5！
也许下面的剧情你已经猜到了——他为此兴奋不已，以至于无法敲键盘。于是，他请你帮忙计算一下，有多少种方案可以让自己的阴谋得逞。
ITX351由此产生了一个邪恶的想法：他想要在这条路上故意把两块
也许下面的剧情你已经猜到了——他为此兴奋不已，以至于无法敲键盘。于是，他请你帮忙计算一下，有多少种方案可以让自己的阴谋得逞。
输入描述:
每个测试点包含多组数据，输入文件的第一行是一个正整数T，表示数据的组数。注意各组数据之间是独立无关的。
接下来T行，每行包含一个正整数N，代表一组数据中路的长度。
输出描述:
输出应包含T行，对于每组数据，输出一个正整数，表示满足条件的方案数。
由于答案可能非常的大，你只需要输出答案对取模后的结果。
备注:
所有测试数据的范围和特点如下表所示：
