{"raw_statement":[{"iden":"background","content":"暴龙爱吃火锅。"},{"iden":"statement","content":"定义 $S(x)$ 表示 $x$ 的每一位的数字之和，例如：$S(14)=1+4=5$，$S(114514)=1+1+4+5+1+4=16.$\n\n另外，定义 $fib(x)$ 代表斐波那契数列的第 $x$ 项，具体地：\n\n$$fib(1)=fib(2)=1,\\ fib(x)=fib(x-1)+fib(x-2)\\ (x≥3).$$\n\n现在给定 $n$，求出下式的值，其中 $\\bmod 9$ 表示对 $9$ 取余数：\n\n$$(S(fib(1))+S(fib(2))+S(fib(3))+...+S(fib(n))) \\bmod 9.$$"},{"iden":"input","content":"第一行一个整数 $T$。\n\n接下来 $T$ 组问询，每次一个整数 $n$。"},{"iden":"output","content":"$T$ 行，每行一个整数代表答案。"},{"iden":"note","content":"【样例解释】\n\n对于第一组询问，$n=7$，答案为： \n\n$$\n\\begin{aligned}\n& \\ \\ \\ \\ \\ (S(fib(1))+S(fib(2))\\ldots+S(fib(6))+S(fib(7)))\\bmod 9 \\\\\n& =(1+1+2+3+5+8+(1+3))\\bmod 9 \\\\\n& =6.\n\\end{aligned}\n$$\n\n---\n\n【数据范围】\n\n**「本题采用捆绑测试」**\n\n- $\\texttt{Subtask 1(10 pts)：}T=1,\\ n\\le 10$；\n- $\\texttt{Subtask 2(30 pts)：}T=10^2,\\ n\\le 10^3$；\n- $\\texttt{Subtask 3(60 pts)：}$无特殊限制。\n\n对于 $100\\%$ 的数据，满足 $1\\le T\\le 10^5,\\ 1\\le n\\le 10^6$。"}],"translated_statement":null,"sample_group":[["3\n7\n14\n114514","6\n5\n8"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}