#P4942. 小凯的数字

    ID: 3871 Type: RemoteJudge 1000ms 128MiB Tried: 7 Accepted: 3 Difficulty: 2 Uploaded By: Tags>模拟数论数学高精度逆元

小凯的数字

题目背景

NOIP2018 原创模拟题T1

NOIP DAY1 T1 or DAY 2 T1 难度

是否发现与NOIP2017 DAY1 T1 有异曲同工之妙

题目描述

小凯有一天突发奇想,写下了一串数字:l(l+1)(l+2)...(r1)r\overline{l(l+1)(l+2)...(r-1)r}

例如:l=2,r=5l=2,r=5时,数字为:23452345

l=8,r=12l=8,r=12时数字为:8910111289101112

小凯很喜欢数字 99,所以他想问你他写下的数字除以 99 的余数是多少

例如:l=2,r=5l=2,r=5时,2345mod9=52345\,\,mod\,\,9 = 5

输入格式

输入格式:

第一行为数字 QQ,表示小凯有 QQ 个问题

22Q+1Q+1 行,每行两个数字 l,rl,r 表示数字范围

输出格式

输出格式:

对于每行的问题输出一行,一个数字,表示小凯问题的回答

2
2 5
8 12
5
5
3
1 999
123 456
13579 24680
0
6
0

提示

样例1解释:2345mod9=52345\,\,mod\,\,9 = 5   89101112mod9=589101112\,\,mod\,\,9 = 5

30% 数据满足:Q10;l,r100Q\leq10;l,r\leq100

50% 数据满足:Q100;l,r10000Q\leq100;l,r\leq10000

70% 数据满足:Q1000;l,r106Q\leq1000;l,r\leq10^6

100%数据满足:Q10000;0<l,r1012Q\leq10000;0<l,r\leq10^{12}lrl\leq r