Background

The T-Rex loves eating Chinese cabbage.

Problem Description

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.

Input Format

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 Format

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

4
5 9
46 50
114 514
19 19810

18
3
1134
74924

Hint

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