小凯的数字

题目背景

NOIP2018 原创模拟题T1 NOIP DAY1 T1 or DAY 2 T1 难度 是否发现与NOIP2017 DAY1 T1 有异曲同工之妙 说明:#10,bug已修复

题目描述

小凯有一天突发奇想,写下了一串数字:$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 mod 9 = 5

输入输出格式

输入格式


输入格式: 第一行为数字Q,表示小凯有Q个问题 第2-Q+1行,每行两个数字 l,r 表示数字范围

输出格式


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

输入输出样例

输入样例 #1

2
2 5
8 12

输出样例 #1

5
5

输入样例 #2

3
1 999
123 456
13579 24680

输出样例 #2

0
6
0

说明

样例1解释:2345 mod 9 = 5   89101112 mod 9 = 5 30% 数据满足:$Q<=10;l,r<=100$ 50% 数据满足:$Q<=100;l,r<=10000$ 70% 数据满足:$Q<=1000;l,r<=10^6$ 100%数据满足:$Q<=10000;0