COCI '19 Contest 1 #1 Trol

View as PDF

Submit solution

Points: 5 (partial)
Time limit: 1.0s
Memory limit: 512M

Problem types
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

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 2^{60} 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 197^{th} 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 l-th to r-th element of A?". Help Stjepan answer those queries!

Input

The first line contains an integer Q (1 \leq Q \leq 100) from the task description. The next Q lines contain two integers l_i and r_i (1 \leq l_i \leq r_i \leq 2^{60}), the parameters of Marin's i-th query.

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.

Scoring

In test cases worth a total of 20% of the points, for each query 1 \leq l_i \leq r_i \leq 9 will hold.

In test cases worth a total of 60% of the points, for each query r_i - l_i \leq 1000 will hold.

Sample Input 1

1
1 5

Sample Output 1

15

Sample Input 2

2
9 13
44 45

Sample Output 2

19
17

Explanation of Sample Output 2

1^{st} \text{ query}\rightarrow A_9 = 9,\ A_{10} = 1 + 0 = 1,\ A_{11} = 1 + 1 = 2,\ A_{12} = 1 + 2 = 3,\ A_{13} = 1 + 3 = 4.

A_9+A_{10}+A_{11}+A_{12}+A_{13}=9+1+2+3+4=19.

2^{nd} \text{ query}\rightarrow A_{44} = 4+4 = 8,\ A_{45} = 4+5= 9. A_{44} + A_{45} = 8 + 9 = 17.

Sample Input 3

1
1998 2018

Sample Output 3

102

Comments

There are no comments at the moment.