Mock CCC '19 Contest 1 S3 - Sum Maximization

View as PDF

Submit solution

Points: 10 (partial)
Time limit: 2.0s
Memory limit: 64M

Author:
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].

Subtasks

For 5/15 of the points, N = 1.

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

There are no comments at the moment.