You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

##题目描述 天才小金热衷于寻找提升自己逼格的数学元素。他经过数日的研究，发现回文数字是很 有逼格的东数学元素。

小金经过严密的数学推演，发现了能够求出特定长度回文数字个数的递推公式，现在他

想知道下式对 $233333$ 取模的答案：

$S[n] =$ $\sum\limits_{i=1}^{n}$ $i × s[i] × (i$%$2)$

其中，$s[i]$ 表示长度为 $i$ 的回文数的个数（不含前导 $0$）。 ##输入格式 第一行一个整数 $T$ 。 接下来 $T$ 行，每行一个整数 $n$ ，含义与题面一致。 ##输出格式 输出共 $T$ 行，每行一个整数，表示题面所求答案。 输入样例

1
2

##输出样例

9

数据范围 对于 30% 的数据，$n ≤ 5$ ；

对于另外 20% 的数据，$∑n ≤ 10^7$ ；

对于另外 20% 的数据，$T = 1$ ；

对于 100% 的数据，$T ≤ 5 × 10^5 , n ≤ 10^9$