CF1796F.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 \lt A$, $1 \le b \lt B$ and $1 \le n \lt N$.

我们称一个正整数三元组 $(a, b, n)$ 为“奇怪的”，如果等式 $\frac{an}{nb} = \frac{a}{b}$ 成立，其中 $an$ 表示将 $a$ 和 $n$ 拼接（即按十进制顺序连接）所得的整数，$nb$ 表示将 $n$ 和 $b$ 拼接所得的整数。在拼接时，所有整数均不带前导零。

例如，若 $a = 1$、$b = 5$、$n = 9$，则该三元组是奇怪的，因为 $\frac{19}{95} = \frac{1}{5}$；但 $a = 7$、$b = 3$、$n = 11$ 不是奇怪的，因为 $\frac{711}{113} \ne \frac{7}{3}$。

给定三个整数 $A$、$B$ 和 $N$，请计算满足 $1 \le a \lt A$、$1 \le b \lt B$ 且 $1 \le n \lt N$ 的奇怪三元组 $(a, b, n)$ 的个数。

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

唯一的一行包含三个整数 $A$、$B$ 和 $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 \lt A$, $1 \le b \lt B$ and $1 \le n \lt N$.

输出一个整数——满足 $1 \le a \lt A$、$1 \le b \lt B$ 且 $1 \le n \lt N$ 的“奇怪三元组” $(a, b, 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$).

在第一个例子中，共有 $7$ 个奇怪三元组：$(1, 1, 1)$、$(1, 4, 6)$、$(1, 5, 9)$、$(2, 2, 2)$、$(2, 5, 6)$、$(3, 3, 3)$ 和 $(4, 4, 4)$。