Trol

Interview

Time limit1sMemory limit512 MB

Summary

Given an array where A[i] is the digital root of i for i from 1 to 260, answer Q queries asking for the sum over a range [l, r].

Level: Easy2 of 10
Topics: Prefix sum, Math, Implementation
Solved: No attempts yet

Problem

Stjepan recently received his bachelor's degree in mathematics from the University of Zagreb. Naturally, his parents are very proud and have decided to give him all positive integers not greater than 260 as a gift. To keep them safe, he quickly stored all of those numbers in an array $A$ , such that $A_i = i$ .

His jealous friend Marin decided to prank him by repeatedly replacing each element of $A$ with the sum of its digits until all elements of $A$ consisted of a single digit. For example, the initial value of the 197th element of $A$ was 197. Marin first changed that value to $1 + 9 + 7 = 17$ and then changed its value again to $1 + 7 = 8$ .

Stjepan is devastated and begs Marin to return his array to its initial state. Unfortunately, Marin won't do that until Stjepan correctly answers his $Q$ queries: "What is the sum of numbers from the $l$ -th to the $r$ -th element of $A$ ?"

Help Stjepan answer those queries!

Input

The first line contains an integer $Q$ from the task description. ( $1 \le Q \le 100$ )

The next $Q$ lines contain two integers $l_i$ and $r_i$ , the parameters of Marin's $i$ -th query. ( $1 \le l_i \le r_i \le 260$ )

Output

Output the answers to each of Marin's $Q$ queries. Each answer should be printed in a separate line and their order should match the order of the queries as they are given in the input.

Examples3

Example 1
Input
```
1
1 5
```
Expected output
```
15
```
Example 2
Input
```
2
9 13
44 45
```
Expected output
```
19
17
```
Example 3
Input
```
1
1998 2018
```
Expected output
```
102
```