P4942 Xiao Kai’s Number

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.

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$.

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.

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

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