题目背景

P 哥是一个经常丢密码条的男孩子。

在 ION8102 赛场上，P 哥又弄丢了密码条，笔试满分的他当然知道这可是要扣 $5$ 分作为惩罚的，于是他开始破解 IONXunil 系统的密码。

题目描述

定义一个串合法，当且仅当串只由 $\verb!A!$ 和 $\verb!B!$ 构成，且没有连续的 $3$ 个 $\verb!A!$。P 哥知道，密码就是长度为 $N$ 的合法字符串数量对 $19260817$ 取模的结果。但是 P 哥不会算，所以他只能把 $N$ 告诉你，让你来算。

至于为什么要对这个数取模，好像是因为纪念某个人，但到底是谁，P 哥也不记得了。

然而他忘记字符串长度 $N$ 应该是多少了，于是他准备试 $M$ 组数据。

输入格式

第一行给出一个整数 $M$ 表示询问次数。

接下来 $M$ 行每行给出一个正整数 $N$，表示该组询问中字符串的长度。

输出格式

对于每一次询问输出一行一个整数表示答案。

3
1
3
6

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$。