Sum Maximization

View as PDF
Submit solution
Points: 10 (partial)
Time limit: 0.5s
Memory limit: 64M
Author:
Ninjaclasher
Problem type

You are given Q queries of the form:

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

Input Specification

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

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

Output Specification

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

Sample Input

2
1 100
1 9995

Sample Output

18
35

Explanation For Sample

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

Comments


  • 0
    Viv_CCGS  commented on April 25, 2024, 12:21 p.m.

    In the sample case, is the first query not 99, as that sums to 18, and not 9?