定义 $S(x)$ 表示 $x$ 的每一位的数字之和，例如：$S(14)=1+4=5$，$S(114514)=1+1+4+5+1+4=16.$
另外，定义 $fib(x)$ 代表斐波那契数列的第 $x$ 项，具体地：
$$fib(1)=fib(2)=1,\ fib(x)=fib(x-1)+fib(x-2)\ (x≥3).$$
现在给定 $n$，求出下式的值，其中 $\bmod 9$ 表示对 $9$ 取余数：
$$(S(fib(1))+S(fib(2))+S(fib(3))+...+S(fib(n))) \bmod 9.$$
第一行一个整数 $T$。
接下来 $T$ 组问询，每次一个整数 $n$。
$T$ 行，每行一个整数代表答案。
【样例解释】
对于第一组询问，$n=7$，答案为：
$$
\begin{aligned}
& \ \ \ \ \ (S(fib(1))+S(fib(2))\ldots+S(fib(6))+S(fib(7)))\bmod 9 \\
& =(1+1+2+3+5+8+(1+3))\bmod 9 \\
& =6.
\end{aligned}
$$
【数据范围】
「本题采用捆绑测试」
-
$\texttt{Subtask 1(10 pts)：}T=1,\ n\le 10$；
-
$\texttt{Subtask 2(30 pts)：}T=10^2,\ n\le 10^3$；
-
$\texttt{Subtask 3(60 pts)：}$无特殊限制。
对于 $100%$ 的数据，满足 $1\le T\le 10^5,\ 1\le n\le 10^6$。