codeforces#P1796F. Strange Triples

Strange Triples

Description

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

Input

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

Output

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

5 6 10
10 10 100
1 10 25
4242 6969 133333337
94841 47471 581818184
7
29
0
19536
98715

Note

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$).