题目描述

有一个特殊的数字序列，按如下规则生成：数字 $1$ 出现 $1$ 次，数字 $2$ 出现 $2$ 次，数字 $3$ 出现 $3$ 次，数字 $4$ 出现 $4$ 次，数字 $5$ 出现 $5$ 次，数字 $6$ 出现 $6$ 次，数字 $7$ 出现 $7$ 次，数字 $8$ 出现 $8$ 次，数字 $9$ 出现 $9$ 次，数字 $10$ 出现 $10$ 次，以此类推，依次拼接而成。

给定多个询问，每次给出两个正整数 $l,r$，求序列中第 $l$ 位到第 $r$ 位的数字之和。

输入格式

输入包含多组测试数据。

第一行一个正整数 $T$。

接下来 $T$ 组问询，每次两个正整数 $l,r$。

输出格式

$T$ 行，每行一个整数代表答案。

样例

4
5 9
46 50
114 514
19 19810

18
3
1134
74924

</p>

提示

样例解释

序列的前若干位为：

$$12233344445555566666677777778888888899999999910101010101010101010\cdots\cdots$$

对于第一组询问，第 $5$ 位到第 $9$ 位的数字之和为 $3+3+4+4+4=18$。

对于第二组询问，第 $46$ 位到第 $50$ 位的数字之和为 $1+0+1+0+1=3$。

---

数据范围

本题采用捆绑测试。

• $\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)：}$无特殊限制。

对于 $100\%$ 的数据，满足 $1\le T\le 10^5$，$1\le l\le r\le 10^6$。