Назовем тройку положительных целых чисел (\(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\) and \(N\). Посчитайте количество странных троек \((a, b, n\)) таких, что \(1 \le a < A\), \(1 \le b < B\) and \(1 \le n < N\).
Выходные данные
Выведите одно целое число — количество странных троек \((a, b, n\)) таких, что \(1 \le a < A\), \(1 \le b < B\) and \(1 \le n < N\).
Примечание
В первом примере \(7\) странных троек: \((1, 1, 1\)), (\(1, 4, 6\)), (\(1, 5, 9\)), (\(2, 2, 2\)), (\(2, 5, 6\)), (\(3, 3, 3\)) and (\(4, 4, 4\)).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5 6 10
|
7
|
|
2
|
10 10 100
|
29
|
|
3
|
1 10 25
|
0
|
|
4
|
4242 6969 133333337
|
19536
|
|
5
|
94841 47471 581818184
|
98715
|