如果等式 $$$\frac{an}{nb} = \frac{a}{b}$$$ 成立,我们称正整数三元组 ($$$a, b, n$$$) 为奇怪,其中 $$$an$$$ 是 $$$a$$$ 和 $$$n$$$ 的串联,而 $$$nb$$$ 是 $$$n$$$ 和 $$$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$$$。计算奇怪三元组 $$$(a, b, n$$$) 的数量,使得 $$$1 \le a < A$$$、$$$1 \le b < B$$$ 和 $$$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$$$ 和 $$$1 \le n < N$$$。
示例
输入 #1
5 6 10
输出 #1
7
输入 #2
10 10 100
输出 #2
29
输入 #3
1 10 25
输出 #3
0
输入#4
4242 6969 133333337
输出#4
19536
输入 #5
94841 47471 581818184
输出 #5
98715
注意
在第一个示例中,有 $$$7$$$ 奇怪的三元组:$$$(1, 1, 1$$$), ($$$1, 4, 6$$$), ($$$1, 5, 9$$$), ($$$2, 2, 2$$$), ($$$2, 5, 6$$$), ($$$3, 3, 3$$$) 和 ($$$4, 4, 4$$$)。