Repeated Digit Count - FAANG Problems | Repovive

FNG2. Repeated Digit Count

2s256 MB

This problem is based on a Meta interview problem described here.

A positive integer is called uniform if all of its digits are the same. For example, $1$ , $22$ , $333$ , $4444$ , and $999999999$ are uniform integers, while $10$ , $121$ , and $9998$ are not.

Given two integers $A$ and $B$ , count the number of uniform integers in the inclusive range $[A, B]$ .

Constraints

$1 \le A \le B \le 10^{12}$

Input

$A \quad B$

Output

$ans$

Samples

Input

75 300

Explanation

\begin{array}{c} \text{Range: } [75, \; 300] \\ \hline \\ \begin{array}{llc} \textbf{Digit Length} & \textbf{Valid Uniform Numbers Found} & \textbf{Count} \\ \hline \text{1-Digit } (1 - 9) & \text{None} & 0 \\ \text{2-Digit } (11 - 99) & 77, \; 88, \; 99 & 3 \\ \text{3-Digit } (111 - 999) & 111, \; 222 & 2 \\ \end{array} \\ \\ \hline \text{\textbf{Final Answer: }} \text{Total Uniforms } = 3 + 2 = \color{cyan}{\mathbf{5}} \end{array}

Output

Input

1 9

Explanation

\begin{array}{c} \text{Range: } [1, \; 9] \\ \hline \\ \begin{array}{llc} \textbf{Digit Length} & \textbf{Valid Uniform Numbers Found} & \textbf{Count} \\ \hline \text{1-Digit } (1 - 9) & 1, \; 2, \; 3, \; 4, \; 5, \; 6, \; 7, \; 8, \; 9 & \mathbf{9} \\ \end{array} \\ \\ \hline \text{\textbf{Final Answer: }} \text{Total Uniforms } = \color{cyan}{\mathbf{9}} \end{array}

Output

Input

5 1111

Explanation

\begin{array}{c} \text{Range: } [5, \; 1111] \\ \hline \\ \begin{array}{llc} \textbf{Digit Length} & \textbf{Valid Uniform Numbers Found} & \textbf{Count} \\ \hline \text{1-Digit } (1 - 9) & 5, \; 6, \; 7, \; 8, \; 9 & 5 \\ \text{2-Digit } (11 - 99) & 11, \; 22, \; 33, \; 44, \; 55, \; 66, \; 77, \; 88, \; 99 & 9 \\ \text{3-Digit } (111 - 999) & 111, \; 222, \; 333, \; 444, \; 555, \; 666, \; 777, \; 888, \; 999 & 9 \\ \text{4-Digit } (1111 - 9999) & 1111 & 1 \\ \end{array} \\ \\ \hline \text{\textbf{Final Answer: }} \text{Total Uniforms } = 5 + 9 + 9 + 1 = \color{cyan}{\mathbf{24}} \end{array}

Output

FNG2. Repeated Digit Count

2s256 MB

This problem is based on a Meta interview problem described here.

A positive integer is called uniform if all of its digits are the same. For example, $1$ , $22$ , $333$ , $4444$ , and $999999999$ are uniform integers, while $10$ , $121$ , and $9998$ are not.

Given two integers $A$ and $B$ , count the number of uniform integers in the inclusive range $[A, B]$ .

Constraints

$1 \le A \le B \le 10^{12}$

Input

$A \quad B$

Output

$ans$

Samples

Input

75 300

Explanation

\begin{array}{c} \text{Range: } [75, \; 300] \\ \hline \\ \begin{array}{llc} \textbf{Digit Length} & \textbf{Valid Uniform Numbers Found} & \textbf{Count} \\ \hline \text{1-Digit } (1 - 9) & \text{None} & 0 \\ \text{2-Digit } (11 - 99) & 77, \; 88, \; 99 & 3 \\ \text{3-Digit } (111 - 999) & 111, \; 222 & 2 \\ \end{array} \\ \\ \hline \text{\textbf{Final Answer: }} \text{Total Uniforms } = 3 + 2 = \color{cyan}{\mathbf{5}} \end{array}

Output

Input

1 9

Explanation

\begin{array}{c} \text{Range: } [1, \; 9] \\ \hline \\ \begin{array}{llc} \textbf{Digit Length} & \textbf{Valid Uniform Numbers Found} & \textbf{Count} \\ \hline \text{1-Digit } (1 - 9) & 1, \; 2, \; 3, \; 4, \; 5, \; 6, \; 7, \; 8, \; 9 & \mathbf{9} \\ \end{array} \\ \\ \hline \text{\textbf{Final Answer: }} \text{Total Uniforms } = \color{cyan}{\mathbf{9}} \end{array}

Output

Input

5 1111

Explanation

\begin{array}{c} \text{Range: } [5, \; 1111] \\ \hline \\ \begin{array}{llc} \textbf{Digit Length} & \textbf{Valid Uniform Numbers Found} & \textbf{Count} \\ \hline \text{1-Digit } (1 - 9) & 5, \; 6, \; 7, \; 8, \; 9 & 5 \\ \text{2-Digit } (11 - 99) & 11, \; 22, \; 33, \; 44, \; 55, \; 66, \; 77, \; 88, \; 99 & 9 \\ \text{3-Digit } (111 - 999) & 111, \; 222, \; 333, \; 444, \; 555, \; 666, \; 777, \; 888, \; 999 & 9 \\ \text{4-Digit } (1111 - 9999) & 1111 & 1 \\ \end{array} \\ \\ \hline \text{\textbf{Final Answer: }} \text{Total Uniforms } = 5 + 9 + 9 + 1 = \color{cyan}{\mathbf{24}} \end{array}

Output