F. Strange Triplestime limit per test10 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputLet'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.InputThe only line contains three integers A, B and N (1 \le A, B \le 10^5; 1 \le N \le 10^9).OutputPrint 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.ExamplesInput
5 6 10
Output
7
Input
10 10 100
Output
29
Input
1 10 25
Output
0
Input
4242 6969 133333337
Output
19536
Input
94841 47471 581818184
Output
98715
NoteIn 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).
5 6 10

7 
['brute force', 'math', 'number theory', '*2900']