烦人的数学作业

题目背景

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

题目描述

Mr.G最近在看一些关于数字题的书,他每天愁同学们太~~聪明~~了,所有的作业同学们都能~~做到全对~~(拿到答案)。Mr.G~~蒙在鼓里~~(心知肚明)。为了使同学们进步,Mr.G总是创造一些~~简单~~(毒瘤)题来作为作业。以下是数学作业的最后一题题干—— 给出一个区间$ L $~$ R $,求$ L $到$ R $区间内**每个数的数字和**,如123这个数的数字和为1+2+3=6。 ($ 1 \leq L \leq R \leq 10^2 $) 同学们纷纷做出来了,Mr.G一看这最后一题跟摆设没区别了呀,于是他迅速修改了题目,把范围定得非常非常大,且有$ T $组数据,将最终的答案mod $ 10^9+7 $。 ($ 1 \leq L \leq R \leq 10^{18} $) ($ 1 \leq T \leq 20 $) 同学们纷纷被难住了。但H为了备战NOIP2018,没有时间完成Mr.G的数学作业~~(其实是不想做QwQ)~~,所以Ta找到了你,希望你帮助Ta和同学完成这烦人的数学作业!

输入输出格式

输入格式


输入共$ T+1 $行, 第$ 1 $行读入$ T $。代表有$ T $组数据; 第$ 2 $~$ T+1 $行。读$ L_i $和$ R_i $

输出格式


输出共$ T $行, 每行输出$ L_i $和$ R_i $的区间数字和mod $ 10^9+7 $。

输入输出样例

输入样例 #1

2
24 69
70 120

输出样例 #1

411
498

说明

对于 $ 50\% $ 的数据,$ 1 \leq L \leq R \leq 10^8 $; 对于 $ 100\% $ 的数据,$ 1 \leq L \leq R \leq 10^{18} $,$ 1 \leq T \leq 20 $。