SP11300 NUMPLAY - Fun with numbers

定义一个数是符合要求的，当且仅当： + 这个数的每个数字只能是 $1$ 或 $3$ 或 $5$ 或 $7$。 + 若这个数字中的一位为 $1$，则下一位只能为 $3$ 或者不接数字。 + 若这个数字中的一位为 $3$，则下一位只能为 $1$ 或 $5$ 或者不接数字。 + 若这个数字中的一位为 $5$，则下一位只能为 $7$ 或者不接数字。 + 若这个数字中的一位为 $7$，则下一位只能为 $3$ 或 $5$ 或者不接数字。 如 $13573$ 是符合要求的，而 $113573$ 是不符合要求的。 请求出位数为 $n$ 的符合要求的数的个数。

第一行一个整数 $t$ 表示数据组数。 接下来 $t$ 行，每行一个数 $n$。

对于每组数据，输出位数为 $n$ 的符合要求的数的个数并换行。

$1\leq t\leq 40,1\leq n\leq 10^4$。 **请注意：答案可能大于 `c++` 中的 `long long` 所能存储的最大数值。**