Digital Root Sum Queries

Stjepan recently earned a Bachelor's degree in Mathematics from the University of Zagreb. His parents, proud as they are, gifted him all positive integers not exceeding $2^{60}$, which he stored in a sequence $A$ such that $A_i=i$. However, his envious friend Marin played a prank by repeatedly replacing every element of $A$ with the sum of its digits until a single digit remained. This final single digit is known as the digital root of the number. In fact, for any positive integer $n$, its digital root can be computed by the formula: $$\text{dr}(n)=1+((n-1)\mod 9).$$

Stjepan is desperate to revert the sequence back to its original state. Marin has agreed to do so only after Stjepan answers $Q$ queries. In each query, given two integers $l$ and $r$, Stjepan must compute the sum of the digital roots of the elements from $A_l$ to $A_r$. Can you help him answer these queries correctly?

inputFormat

The first line contains a single integer $Q$ ($1\le Q\le 10^5$), the number of queries. Each of the following $Q$ lines contains two space-separated positive integers $l$ and $r$ ($1\le l\le r\le 2^{60}$), representing a query.

outputFormat

For each query, output one line containing the sum of the digital roots of $A_l, A_{l+1}, \dots, A_r$.

sample

1
1 9

45