A15671. Strange Triples

Let's call a triple of positive integers ( $a, b, n$ ) strange if the equality $\frac{an}{nb} = \frac{a}{b}$ holds, where $an$ is the concatenation of $a$ and $n$ and $nb$ is the concatenation of $n$ and $b$ . For the purpose of concatenation, the integers are considered without leading zeroes.

For example, if $a = 1$ , $b = 5$ and $n = 9$ , then the triple is strange, because $\frac{19}{95} = \frac{1}{5}$ . But $a = 7$ , $b = 3$ and $n = 11$ is not strange, because $\frac{711}{113} \ne \frac{7}{3}$ .

You are given three integers $A$ , $B$ and $N$ . Calculate the number of strange triples $(a, b, n$ ), such that $1 \le a < A$ , $1 \le b < B$ and $1 \le n < N$ .

The only line contains three integers $A$ , $B$ and $N$ ( $1 \le A, B \le 10^5$ ; $1 \le N \le 10^9$ ).

Print one integer — the number of strange triples $(a, b, n$ ) such that $1 \le a < A$ , $1 \le b < B$ and $1 \le n < N$ .

In the first example, there are $7$ strange triples: $(1, 1, 1$ ), ( $1, 4, 6$ ), ( $1, 5, 9$ ), ( $2, 2, 2$ ), ( $2, 5, 6$ ), ( $3, 3, 3$ ) and ( $4, 4, 4$ ).