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.