Description

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.

Input Format

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 Format

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

1
1 5

15

2
9 13
44 45

19
17

1
1998 2018

102

Hint

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 CONTEST #1 T1 Trol .

Translated by ChatGPT 5