Background

Brother P is a boy who often loses his password slips.

At the ION8102 contest site, Brother P lost his password slip again. As someone who can get full marks on the written test, he of course knows that this will cost him $5$ points as a penalty, so he started cracking the password of the IONXunil system.

Problem Description

Define a string as valid if and only if it is made up only of $\verb!A!$ and $\verb!B!$, and it does not contain $3$ consecutive $\verb!A!$ characters. Brother P knows that the password is the number of valid strings of length $N$, taken modulo $19260817$. But Brother P cannot compute it, so he can only tell you $N$ and ask you to compute it.

As for why the result is taken modulo this number, it seems to be in memory of someone, but who exactly that is, Brother P does not remember either.

However, he forgot what the string length $N$ should be, so he plans to try $M$ sets of testdata.

Input Format

The first line gives an integer $M$, which represents the number of queries.

Then follow $M$ lines, each giving a positive integer $N$, meaning the length of the string in that query.

Output Format

For each query, output one integer per line, representing the answer.

3
1
3
6

2
7
44

Hint

Explanation of the samples.

When the length is $1$, there are only two arrangements: $\verb!A!$ and $\verb!B!$, and both are valid.

When the length is $3$, all strings are valid except $\verb!AAA!$, so there are $2^3-1$ strings.

Constraints.

• For $20\%$ of the testdata, all $N\leq20$, $M\leq2$.
• For $70\%$ of the testdata, all $N\leq10^7$.
• For $100\%$ of the testdata, all $N\leq10^9$, $M\leq10$.

Translated by ChatGPT 5