#P14874. [OOI2023预选赛]Special Numbers特殊数

    ID: 14090 传统题 1000ms 256MiB 尝试: 1 已通过: 1 难度: 7 上传者: 标签>CF2200提高数位 DP前缀和优化 DP对称性分析上界限制状态

[OOI2023预选赛]Special Numbers特殊数

题目描述

如果一个数从左往右读和从右往左读完全相同,则称它为回文数。

如果一个数 aa 是回文数,并且 11⋅a11 \cdot a 也是回文数,则称 aa 为特殊数。

给定 nn 个询问。对于每个询问 aia_i,你需要求出 11 到 aia_i 之间有多少个特殊数。由于答案可能很大,请对 109+710^9+7 取模。

输入格式

第一行包含一个整数 nn,表示询问数量。

接下来 nn 行,每行包含一个整数 aia_i,表示一个询问。

输出格式

对于每个询问,输出一行一个整数,表示 11 到 aia_i 中特殊数的数量,结果对 109+710^9+7 取模。

数据范围

1≤n≤10001 \le n \le 1000,1≤ai≤1050001 \le a_i \le 10^{5000}。

注意:aia_i 非常大,需要按字符串处理。

样例

5
10
45
79
113
467
9
13
13
15
43

样例解释

当 ai=10a_i=10 时,小于等于 1010 的特殊数为 1,2,3,4,5,6,7,8,91,2,3,4,5,6,7,8,9。

当 ai=45a_i=45 时,特殊数为 1,2,3,4,5,6,7,8,9,11,22,33,441,2,3,4,5,6,7,8,9,11,22,33,44。

子任务

组别 分数 aia_i 限制 nn 限制 依赖 备注
0 - 样例
1 15 ai≤70000a_i \le 70000 n≤100n \le 100 0
2 9 ai≤2⋅106a_i \le 2\cdot 10^6 - 0,1
3 14 ai≤108a_i \le 10^8 n≤100n \le 100
4 11 ai≤1011a_i \le 10^{11} - 0--3
5 25 ai≤1018a_i \le 10^{18} 0--4
6 26 - 0--5 Offline 检查