题目描述

小 A 写了一个 N×M 的矩阵 A，我们看不到这个矩阵，但我们可以知道，其中第 i 行第 j 列的元素 Ai,j​ 是 i 和 j 的 公倍数（i=1,…,N,j=1,…,M）。现在有 K 个小朋友，其中第 k 个小朋友想知道，矩阵 A 中最多有多少个元素可以是 k（k=1,2,…,K）。请你帮助这些小朋友求解。

注意：每位小朋友的答案互不相关，例如，有些位置既可能是 x，又可能是 y，则它同可以时满足 x,y 两名小朋友的要求。

方便起见，你只需要输出 ∑k=1K​k×ansk​ 即可，其中 ansk​ 表示第 k 名小朋友感兴趣的答案。

输入格式

一行三个正整数 N,M,K。

输出格式

输出一行，即 ∑k=1K​k×ansk​。

请注意，这个数可能很大，使用 C++ 语言的选手请酌情使用long long 等数据类型存储答案。

输入输出样例

输入 #1

2 5 2

输出 #1

9

输入 #2

100 100 100

输出 #2

185233

说明/提示

样例 1 解释

只有 A1,1​ 可以是 1，其余都不行。 A1,1​,A1,2​,A2,1​,A2,2​ 都可以是 2，而其余不行。

因此答案是 1×1+2×4=9。

数据规模与约定

• 对于 30% 的测试点，保证 N,M,K≤10；
• 对于 60% 的测试点，保证 N,M,K≤500；
• 对于 100% 的测试点，保证 1≤N,M≤10^5，1≤K≤10^6。