Problem Description

Little $A$ has written a matrix $A$ of size $N \times M$. Although we cannot see this matrix, we know that the element at the $i$-th row and $j$-th column, denoted as $A_{i,j}$, is the least common multiple of $i$ and $j$ ($i=1,\dots,N, j=1,\dots,M$). Now, there are $K$ children, and the $k$-th child wants to know the maximum number of elements in the matrix that can be $k$ ($k=1,2,\dots,K$). Please help these children find the answers.

Note: Each child's answer is independent. For example, some positions can be both $x$ and $y$, so they can satisfy the requirements of both children $x$ and $y$.

For convenience, you only need to output $\sum_{k=1}^{K} k \times ans_k$, where $ans_k$ represents the answer that the $k$-th child is interested in.

Input Format

A single line containing three positive integers $N, M, K$.

Output Format

Output a single line, which is $\sum_{k=1}^{K} k \times ans_k$.

Please note that this number may be very large, so contestants using C++ should consider using data types like long long to store the answer.

Sample Input and Output

Sample Input #1

2 5 2

Sample Output #1

9

Sample Input #2

100 100 100

Sample Output #2

185233

Notes

Explanation of Sample 1

Only $A_{1,1}$ can be $1$, and the rest cannot.
$A_{1,1}, A_{1,2}, A_{2,1}, A_{2,2}$ can all be $2$, but the rest cannot.

Thus, the answer is $1 \times 1 + 2 \times 4 = 9$.

Data Size and Constraints

• For $30\%$ of the test cases, it is guaranteed that $N, M, K \leq 10$;
• For $60\%$ of the test cases, it is guaranteed that $N, M, K \leq 500$;
• For $100\%$ of the test cases, it is guaranteed that $1 \leq N, M \leq 10^5$ and $1 \leq K \leq 10^6$.

见题面 Input 部分

见题面 Output 部分