Submit solution

Points:
10 (partial)

Time limit:
0.5s

Memory limit:
64M

Author:

Problem type

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

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 .

#### 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.

## Comments