#Algo0809. 烦人的数学作业

烦人的数学作业

题目背景

NOIP2018初赛结束了,但H还是要上学的啊啊。。上学肯定要完成老师布置的作业,H十分头疼。在如山的作业中,Mr.G布置的数学作业最烦人,H总是完不成~~

题目描述

Mr.G最近在看一些关于数字题的书,他每天愁同学们太聪明了,所有的作业同学们都能做到全对(拿到答案)。Mr.G蒙在鼓里(心知肚明)。为了使同学们进步,Mr.G总是创造一些简单(毒瘤)题来作为作业。以下是数学作业的最后一题题干——

给出一个区间L L ~R R ,求L L R R 区间内每个数的数字和,如123这个数的数字和为1+2+3=6。

1LR102 1 \leq L \leq R \leq 10^2

同学们纷纷做出来了,Mr.G一看这最后一题跟摆设没区别了呀,于是他迅速修改了题目,把范围定得非常非常大,且有T T 组数据,将最终的答案mod 109+7 10^9+7

1LR1018 1 \leq L \leq R \leq 10^{18} ) (1T20 1 \leq T \leq 20

同学们纷纷被难住了。但H为了备战NOIP2018,没有时间完成Mr.G的数学作业~~(其实是不想做QwQ)~~,所以Ta找到了你,希望你帮助Ta和同学完成这烦人的数学作业!

输入格式

输入共T+1 T+1 行,

1 1 行读入T T 。代表有T T 组数据;

2 2 ~T+1 T+1 行。读Li L_i Ri R_i

输出格式

输出共T T 行,

每行输出Li L_i Ri R_i 的区间数字和mod 109+7 10^9+7

2
24 69
70 120
411
498

提示

对于 50% 50\% 的数据,1LR108 1 \leq L \leq R \leq 10^8

对于 100% 100\% 的数据,1LR1018 1 \leq L \leq R \leq 10^{18} 1T20 1 \leq T \leq 20