题目背景

暴龙爱吃火锅。

题目描述

定义 $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$。