16008 - 小凯的数字

小凯有一天突发奇想,写下了一串数字: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 ≤ 10000), 表示小凯有Q个问题,第2到Q + 1行,每行两个数字l, r(0 < l, r ≤ 10^12, l ≤ r) 表示数字范围

输出

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

样例

输入

2
2 5
8 12

输出

5
5

输入

3
1 999
123 456
13579 24680

输出

0
6
0
时间限制 1 秒
内存限制 128 MB
讨论 统计
上一题 下一题