Background

NOIP 2018 original mock contest problem T1.

Difficulty: similar to NOIP Day 1 T1 or Day 2 T1.

Did you notice that it is somewhat similar in spirit to NOIP 2017 Day 1 T1.

Problem Description

One day, Xiao Kai had a sudden idea 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 really likes the digit $9$, so he wants to ask you: what is the remainder when the number he wrote is divided by $9$?

For example, when $l=2, r=5$, $2345 \bmod 9 = 5$.

Input Format

The first line contains an integer $Q$, meaning Xiao Kai has $Q$ queries.

Lines $2$ to $Q+1$ each contain two integers $l, r$, representing the range of numbers.

Output Format

For each query, output one line with one integer, which is the answer to Xiao Kai’s query.

2
2 5
8 12

5
5

3
1 999
123 456
13579 24680

0
6
0

Hint

Explanation of Sample 1: $2345 \bmod 9 = 5$, and $89101112 \bmod 9 = 5$.

For $30\%$ of the testdata: $Q \leq 10$, and $l, r \leq 100$.

For $50\%$ of the testdata: $Q \leq 100$, and $l, r \leq 10000$.

For $70\%$ of the testdata: $Q \leq 1000$, and $l, r \leq 10^6$.

For $100\%$ of the testdata: $Q \leq 10000$, $0 < l, r \leq 10^{12}$, and $l \leq r$.

Translated by ChatGPT 5