已知一个数列的通项公式是： - $a_1=2$ - $a_2=3$ - $a_n=3a_{n-1}-2a_{n-2}\ (n\gt 2)$ 试求这个数列的前 $n$ 项和 $S_n$ 为多少。 结果可能很大，输出对 $9973$ 取模后的结果即可。

第一行包含一个整数 $T$，表示测试数据组数。 每组测试数据占一行，包含一个整数 $n$. - $T\le 100$ - $1\le n\le 10^9$

对于每组测试数据，在一行内输出一个整数，表示 $S_n$ 对 $9973$ 取模后的结果。