Nice Pairs

Time limit2sMemory limit512 MB

Summary

Count pairs (x, y) with A <= x < y <= B where y is a rotation of x's digits (a suffix moved to the front), counting duplicates only once.

Level: Medium5 of 10
Topics: String, Math, Hash map, Brute force
Solved: No attempts yet

Problem

Two natural numbers $n$ and $m$ form a nice pair when the following holds.

Cutting some digits off the back of $n$ and placing them, in the same order, in front of what is left gives $m$ .

For example, cutting $345$ off the back of $12345$ and placing it in front gives $34512$ , so $(12345, 34512)$ is a nice pair.

You are given two natural numbers $A$ and $B$ with the same number of digits. Count the pairs $(x, y)$ with $A \le x < y \le B$ such that $(x, y)$ is a nice pair.

Two different cut lengths can produce the same $m$ . In that case the pair $(x, y)$ is counted once.

Input

The first line contains two natural numbers $A$ and $B$ separated by a space. $1 \le A \le B \le 2{,}000{,}000$ , and $A$ and $B$ have the same number of digits.

Output

Print the number of nice pairs as a single integer.

Examples3

Example 1
Input
```
1 9
```
Expected output
```
0
```
Example 2
Input
```
10 40
```
Expected output
```
3
```
Example 3
Input
```
100 500
```
Expected output
```
156
```