Valid String Count

A string is defined as valid if and only if it is composed solely of the characters A and B, and it does not contain three consecutive As. P, however, only remembers that the password is the number of valid strings of length N taken modulo $19260817$. Due to a commemorative reason (whose details have been forgotten), the modulo is taken with respect to $19260817$.

The underlying recurrence relation is given by

$f(n)=f(n-1)+f(n-2)+f(n-3)$ for $n\geq 3$, with the base cases $f(0)=1$, $f(1)=2$, and $f(2)=4$.

You are provided with M test cases. For each test case, you are given an integer N (the length of the string). Your task is to compute and output the number of valid strings of length N modulo $19260817$.

inputFormat

The first line contains a single integer M, representing the number of test cases.

Each of the following M lines contains one integer N, which denotes the length of the string.

outputFormat

For each test case, output a single integer on a new line: the number of valid strings of length N taken modulo $19260817$.

sample

3
0
1
2

1
2
4