P7199 [COCI 2019/2020 #1] Trol

Stjepan has recently obtained a bachelor’s degree in mathematics at the University of Zagreb. Naturally, his parents are proud of him and decided to give him all positive integers not exceeding $2^{60}$ as a gift. To keep them safe, he quickly stored all the numbers into a sequence $A$, where $A_i=i$. A friend of his, Marin, who is jealous of him, decided to play a prank: **repeatedly replace every element in $A$ with the sum of its digits, until it eventually becomes a single-digit number.** For example, the initial value of the $197$-th element is $197$. Marin first changed it to $1+9+7=17$, and then changed it once more to $1+7=8$. Stjepan was extremely shocked and asked Marin to restore the sequence to its initial state. Unfortunately, Marin will not do so until Stjepan correctly answers $Q$ queries. For each query, Stjepan needs to answer the sum of the elements from the $l$-th to the $r$-th term in the sequence $A$. Help Stjepan answer these queries.

The first line contains an integer $Q$, the number of queries. The next $Q$ lines each contain two positive integers $l_i, r_i$, representing the interval range of Marin’s $i$-th query.

Output the answers to the $Q$ queries. Separate answers with newline characters, and output them in the order of the queries.

#### Constraints For $20\%$ of the testdata, all queries satisfy $1 \le l_i \le r_i \le 9$. For $60\%$ of the testdata, all queries satisfy $r_i-l_i \le 1000$. For $100\%$ of the testdata, $1 \le Q \le 100$, and all queries satisfy $1 \le l_i \le r_i \le 2^{60}$. #### Notes **The scoring of this problem follows the original COCI problem settings, with a full score of $50$.** **This problem is translated from [COCI2019-2020](https://hsin.hr/coci/archive/2019_2020/) [CONTEST #1](https://hsin.hr/coci/archive/2019_2020/contest1_tasks.pdf) _T1 Trol_ .** Translated by ChatGPT 5