Background

The T-Rex loves eating hotpot.

Problem Description

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.$$

Input Format

The first line contains an integer $T$.

Then follow $T$ queries, each containing one integer $n$.

Output Format

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

3
7
14
114514

6
5
8

Hint

[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