题目描述

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

如果一个数 $a$ 是回文数，并且 $11 \cdot a$ 也是回文数，则称 $a$ 为特殊数。

给定 $n$ 个询问。对于每个询问 $a_i$，你需要求出 $1$ 到 $a_i$ 之间有多少个特殊数。由于答案可能很大，请对 $10^9+7$ 取模。

输入格式

第一行包含一个整数 $n$，表示询问数量。

接下来 $n$ 行，每行包含一个整数 $a_i$，表示一个询问。

输出格式

对于每个询问，输出一行一个整数，表示 $1$ 到 $a_i$ 中特殊数的数量，结果对 $10^9+7$ 取模。

数据范围

$1 \le n \le 1000$，$1 \le a_i \le 10^{5000}$。

注意：$a_i$ 非常大，需要按字符串处理。

样例

5
10
45
79
113
467

9
13
13
15
43

样例解释

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

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

子任务