P8377 [PFOI Round1] T-Rex Hotpot

The T-Rex loves eating hotpot.

Define $S(x)$ as the sum of the digits of $x$. For example, $S(14)=1+4=5$, and $S(114514)=1+1+4+5+1+4=16.$ Also, define $fib(x)$ as the $x$-th term of the Fibonacci sequence. Specifically: $$fib(1)=fib(2)=1,\ fib(x)=fib(x-1)+fib(x-2)\ (x\ge 3).$$ Given $n$, compute the value of the following expression, where $\bmod 9$ means taking the remainder modulo $9$: $$(S(fib(1))+S(fib(2))+S(fib(3))+...+S(fib(n))) \bmod 9.$$

The first line contains an integer $T$. Then follow $T$ queries, each containing one integer $n$.

Output $T$ lines, each line containing one integer representing the answer.

[Sample Explanation] For the first query, $n=7$, the answer is: $$ \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} $$ --- [Constraints] **This problem uses bundled testdata.** - $\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): }$ no special constraints. For $100\%$ of the data, $1\le T\le 10^5,\ 1\le n\le 10^6$. Translated by ChatGPT 5