P哥破解密码
题目背景
P 哥是一个经常丢密码条的男孩子。
在 ION8102 赛场上，P 哥又弄丢了密码条，笔试满分的他当然知道这可是要扣 $5$ 分作为惩罚的，于是他开始破解 IONXunil 系统的密码。
题目描述
定义一个串合法，当且仅当串只由 $\verb!A!$ 和 $\verb!B!$ 构成，且没有连续的 $3$ 个 $\verb!A!$。P 哥知道，密码就是长度为 $N$ 的合法字符串数量对 $19260817$ 取模的结果。但是 P 哥不会算，所以他只能把 $N$ 告诉你，让你来算。
至于为什么要对这个数取模，好像是因为纪念某个人，但到底是谁，P 哥也不记得了。
然而他忘记字符串长度 $N$ 应该是多少了，于是他准备试 $M$ 组数据。
输入输出格式
输入格式
第一行给出一个整数 $M$ 表示询问次数。
接下来 $M$ 行每行给出一个正整数 $N$，表示该组询问中字符串的长度。
输出格式
对于每一次询问输出一行一个整数表示答案。
输入输出样例
输入样例 #1
3
1
3
6
输出样例 #1
2
7
44
说明
### 样例部分解释 :。
长度为 $1$ 时只有 $\verb!A!$ 和 $\verb!B!$ 两种排列，都是合法的。
长度为 $3$ 时除了 $\verb!AAA!$ 是不合法的其他都是可以的，故有 $2^3-1$ 种。
### 数据范围。
- 对于 $20\%$ 数据，全部 $N\leq20$，$M\leq2$；
- 对于 $70\%$ 数据，全部 $N\leq10^7$；
- 对于 $100\%$ 数据，全部 $N\leq10^9$，$M\leq10$。