## Mock CCC '19 Contest 1 S3 - Sum Maximization

View as PDF

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

Author:
Problem type

You are given queries of the form:

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

#### Input Specification

The first line will contain the integer .

The next lines will each contain the integers, .

#### Output Specification

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

For 5/15 of the points, .

#### Sample Input

2
1 100
1 9995

#### Sample Output

18
35

#### Explanation For Sample

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