Problem Background

NOIP2018 Original Simulation Question T1

NOIP DAY1 T1 or DAY2 T1 Difficulty

Notice the similarity to NOIP2017 DAY1 T1

Problem Description

One day, Xiao Kai had a sudden inspiration and wrote down a sequence of numbers: $\overline{l(l+1)(l+2)...(r-1)r}$

For example: When $l=2, r=5$, the number is: $2345$

When $l=8, r=12$, the number is: $89101112$

Xiao Kai loves the number $9$, so he wants to know the remainder of the number he wrote divided by $9$

For example: When $l=2, r=5$, $2345 \mod 9 = 5$

Input Format

The first line contains a number $Q$, indicating that Xiao Kai has $Q$ questions.

From the second line to the $Q+1$-th line, each line contains two numbers $l, r$ representing the range of numbers.

Output Format

For each question, output one line containing a single number, which is the answer to Xiao Kai's question.

Sample Input and Output

Sample Input #1

2
2 5
8 12

Sample Output #1

5
5

Sample Input #2

3
1 999
123 456
13579 24680

Sample Output #2

0
6
0

Notes

Sample 1 Explanation: $2345 \mod 9 = 5$ $89101112 \mod 9 = 5$

30% of the data satisfies: $Q \leq 10; l, r \leq 100$

50% of the data satisfies: $Q \leq 100; l, r \leq 10000$

70% of the data satisfies: $Q \leq 1000; l, r \leq 10^6$

100% of the data satisfies: $Q \leq 10000; 0 < l, r \leq 10^{12}$ and $l \leq r$

见题面 Input 部分

见题面 Output 部分