题目描述

小青在数学探索中发现了一类特殊的数字——回文数。回文数是指正读和反读都相同的数字，例如 1、2、...、9、11、22、101 等都是回文数。这些数字具有独特的对称美，就像数学世界中的艺术品。

小青对回文数产生了浓厚的兴趣，他想：在所有的正整数中，长度不超过 n 的回文数究竟有多少个呢？这个问题看似简单，但当 n 的值很大时，计算起来就不容易了。

请你帮助小青编写一个程序，计算长度不大于 n 的回文数的个数。由于结果可能非常大，请将答案对 10^9+7 取模。

让我们一起探索回文数的奇妙世界，感受数学的对称之美吧！

输入格式

输入一个 T(T<=100) 表示 T 组数据，对于每组数据输入一个 n(1<=n<=1e6)

输出格式

对于每组数据输出一个数表示结果，每个结果占一行

样例

样例 1

输入 # 1

2
1
2

输出 # 1

10
19