说明

因为最近身边的脱单的人太多了，于是GBX狂热的迷上了回文数。因为回文数看起来就像是一对恩爱狗站在一起，他希望自己将来也有那么一天（虽然并不可能）。这一天他突然想到一个问题，长度不大于n的数字有多少是回文数？因为数据很大，所以最后的结果请对1e9+7取模

输入格式

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

输出格式

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

2
1
2

10
19

Source