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