P8577 [CoE R5] T-Rex’s Chinese Cabbage

The T-Rex loves eating Chinese cabbage.

You are given a string formed by concatenating, in order: $1$ copy of $\texttt{1}$, $2$ copies of $\texttt{2}$, $3$ copies of $\texttt{3}$, $4$ copies of $\texttt{4}$, $5$ copies of $\texttt{5}$, $6$ copies of $\texttt{6}$, $7$ copies of $\texttt{7}$, $8$ copies of $\texttt{8}$, $9$ copies of $\texttt{9}$, $10$ copies of $\texttt{10}$, and so on. For each query, find the sum of the digits from position $l$ to position $r$ in the string.

**The input contains multiple groups of testdata.** The first line contains a positive integer $T$. The next $T$ queries each contain two positive integers $l, r$.

Output $T$ lines, each containing one integer representing the answer.

**Sample Explanation** The string is: $$\texttt{12233344445555566666677777778888888899999999910101010101010101010}\cdots\cdots$$ For the first query, the sum of the digits from position $5$ to position $9$ is $3+3+4+4+4=18$. For the second query, the sum of the digits from position $46$ to position $50$ is $1 + 0 + 1 + 0 + 1 = 3$. ------------ **Constraints** **This problem uses bundled tests.** - $\texttt{Subtask 1(10 pts):}T=1$, $1\le l\le r\le 10$; - $\texttt{Subtask 2(20 pts):}1\le T\le 10$, $1\le l\le r\le 10^3$; - $\texttt{Subtask 3(30 pts):}1\le T\le 10^3$, $1\le l\le r\le 10^5$; - $\texttt{Subtask 4(40 pts):}$ no special constraints. For $100\%$ of the data, $1\le T\le 10^5$, $1\le l\le r\le 10^6$. Translated by ChatGPT 5