SP3924 BYTESH1 - Filchs Dilemna
题目描述
霍格沃茨的管理员费尔奇接到任务，需要用地毯铺设通向学校的道路。道路宽度为 2 单位，长度为 $N$ 单位。他只有两种地毯：一种是 1x2 的长条形地毯，另一种是占据三个单位面积的 L 形地毯。以下是这两种地毯的形状：
费尔奇可以在铺设时旋转地毯，并且这两种地毯数量无限。由于他是个不会施魔法的哑炮，只能用逻辑计算出铺路的所有可能方式。他希望算出铺设方法的总数。
例如，对于一条 2x3 的道路，有以下 5 种不同的铺设方法：
在这些方法中，两种地毯可以同时使用，比如铺设 2x4 道路的方法如下：
现在，给定 $N$，你需要帮助费尔奇计算铺设 2x$N$ 道路的不同方法数。由于数字可能很大，只需输出最后四位数字。例如，对于 2x13 的道路，方法数是 13465，你应该输出 3465。如果方法数少于四位数，打印完整数字。比如，当 $N=3$ 时，你应输出 5。
输入格式
第一行包含一个整数 $T$ ($1 \le T \le 100$)，表示测试用例的数量。接下来的 $T$ 行每行包含一个整数 $N$ ($1 \le N \le 1000000$)，表示道路的长度。
输出格式
对于每个测试用例，输出铺设 2x$N$ 道路的最后四位数字的方法数。如果方法数少于四位，直接输出完整数字。
**重要说明：如果最后四位数字中有前导零，去掉前导零后再输出。**
**本翻译由 AI 自动生成**