[PFOI Round1] 暴龙的火锅

暴龙爱吃火锅。

定义 $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$ 行，每行一个整数代表答案。

3
7
14
114514

6
5
8

【样例解释】 对于第一组询问，$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$。