Problem Description

Stjepan recently earned his bachelor's degree in mathematics from the University of Zagreb. His parents are naturally proud of him and decided to gift him all positive integers not exceeding \(2^{60}\). To ensure their safety, he quickly stored all these numbers into a sequence \(A\) such that \(A_i = i\).

A jealous friend of his, Marin, decided to play a prank: continuously replace each element in \(A\) with the sum of its digits until only a single digit remains.

For example, the 197th element initially has the value 197. Marin first changes this value to \(1 + 9 + 7 = 17\), and then changes it again to \(1 + 7 = 8\).

Stjepan is extremely shocked and requests Marin to revert the sequence to its original state. Unfortunately, Marin won't do so until Stjepan correctly answers \(Q\) queries. For each query, Stjepan needs to answer the sum of elements from the \(l\)-th to the \(r\)-th in sequence \(A\).

Help Stjepan answer these queries!

Input Format

The first line contains an integer \(Q\), representing the number of queries.

The next \(Q\) lines each contain two positive integers \(l_i\) and \(r_i\), representing the range of the \(i\)-th query.

Output Format

Output the answers to the \(Q\) queries. Each answer should be separated by a newline and should be in the order of the queries.

Sample Input and Output

Sample Input #1

1
1 5

Sample Output #1

15

Sample Input #2

2
9 13
44 45

Sample Output #2

19
17

Sample Input #3

1
1998 2018

Sample Output #3

102

Notes/Hints

Data Size and Constraints

For 20% of the data, all queries satisfy \(1 \le l_i \le r_i \le 9\).

For 60% of the data, all queries satisfy \(r_i - l_i \le 1000\).

For 100% of the data, \(1 \le Q \le 100\), and all queries satisfy \(1 \le l_i \le r_i \le 2^{60}\).

Notes

This problem's score is set according to the original COCI contest, with a maximum score of 50.

The problem is translated from COCI2019-2020 CONTEST #1 T1 Trol.

见题面 Input 部分

见题面 Output 部分