Sum Maximization

Points: 10 (partial)

Time limit: 0.5s

Memory limit: 64M

Author:

Problem type

You are given $Q$ $Q$ queries of the form:

N M Find the maximum possible sum of the digits (in base $10$ $10$ ) of a positive integer in the range $[N, M]$ $[N, M]$ .

The first line will contain the integer $Q$ $Q$ $(1 \le Q \le 10^4)$ $(1 \leq Q \leq 10^{4})$ .

The next $Q$ $Q$ lines will each contain the integers, $N, M$ $N, M$ $(1 \le N \le M \le 10^{15})$ $(1 \leq N \leq M \leq 10^{15})$ .

For each query, print the maximum possible sum of the digits (in base $10$ $10$ ) of a positive integer in the range $[N, M]$ $[N, M]$ .

Copy

2
1 100
1 9995

Copy

18
35

For the second query, the sum of digits of $9989$ $9989$ is $35$ $35$ , which is the maximum value.

Comments