题目描述

我想知道：

其中$s[i]$是长度为$i$的回文数个数(不含前导0)，最后面的括号是布尔表达式，也就是说，只有在$i$为奇数时表达式为1。

输入格式

第一行一个正整数$T$。

接下来$T$行，每行一个正整数$n$。

输出格式

输出一共$T$行，每行一个整数。表示$S[n] \% 233333$

样例

样例1

9
1
2
3
4
7
10
20
100
100000

9
9
279
279
67779
177780
12700
191255
180559

数据范围

对于$30\%$的数据：$n \le 5$

对于另外$20\%$的数据：$\sum{n}\le 10^7$

对于另外$20\%$的数据：$T==1$

对于$100\%$的数据：$T\le 5*10^5,n\le 10^9$

Ps:注意模数。