You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

NOIP2018 原创模拟题 T1

NOIP DAY1 T1 or DAY2 T1 难度

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

题目描述

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

例如：$l=2,r=5$ 时，数字为：$2345$。

$l=8,r=12$ 时数字为：$89101112$。

小凯很喜欢数字 $9$，所以他想问你他写下的数字除以 $9$ 的余数是多少？

例如：$l=2,r=5$ 时，$2345\bmod9 = 5$。

输入格式

第一行为数字 $Q$,表示小凯有 $Q$ 个问题。

第 $2$ 到 $Q+1$ 行，每行两个数字 $l,r$ 表示数字范围。

输出格式

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

2
2 5
8 12

5
5

3
1 999
123 456
13579 24680

0
6
0

提示

样例 1 解释：$2345\bmod9 = 5$，$89101112\bmod9 = 5$。

对于 $30\%$ 数据满足：$Q\leq10;l,r\leq100$。

对于 $50\%$ 数据满足：$Q\leq100;l,r\leq10000$。

对于 $70\%$ 数据满足：$Q\leq1000;l,r\leq10^6$。

对于 $100\%$ 数据满足：$Q\leq10000;0<l,r\leq10^{12}$ 且 $l\leq r$。