F. Странные тройки
ограничение по времени на тест
10 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Назовем тройку положительных целых чисел ($$$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, B \le 10^5$$$; $$$1 \le N \le 10^9$$$).

Выходные данные

Выведите одно целое число — количество странных троек $$$(a, b, n$$$) таких, что $$$1 \le a < A$$$, $$$1 \le b < B$$$ and $$$1 \le n < N$$$.

Примеры
Входные данные
5 6 10
Выходные данные
7
Входные данные
10 10 100
Выходные данные
29
Входные данные
1 10 25
Выходные данные
0
Входные данные
4242 6969 133333337
Выходные данные
19536
Входные данные
94841 47471 581818184
Выходные данные
98715
Примечание

В первом примере $$$7$$$ странных троек: $$$(1, 1, 1$$$), ($$$1, 4, 6$$$), ($$$1, 5, 9$$$), ($$$2, 2, 2$$$), ($$$2, 5, 6$$$), ($$$3, 3, 3$$$) and ($$$4, 4, 4$$$).