In a two-dimensional plane, we have a rectangle R whose vertices are (0,0), (W,0), (0,H), and (W,H), where W and H are positive integers. Here, find the number of triangles \Delta in the plane that satisfy all of the following conditions:

* Each vertex of \Delta is a grid point, that is, has integer x- and y-coordinates.
* \Delta and R shares no vertex.
* Each vertex of \Delta lies on the perimeter of R, and all the vertices belong to different sides of R.
* \Delta contains at most K grid points strictly within itself (excluding its perimeter and vertices).

Constraints

* 1 \leq W \leq 10^5
* 1 \leq H \leq 10^5
* 0 \leq K \leq 10^5

Input

Input is given from Standard Input in the following format:


W H K


Output

Print the answer.

Examples

Input

2 3 1


Output

12


Input

5 4 5


Output

132


Input

100 100 1000


Output

461316
#include <bits/stdc++.h>
#define long long long int
using namespace std;

// @author: pashka

int gcd(int a, int b) {
    while (b > 0) {
        int c = a % b;
        a = b;
        b = c;
    }
    return a;
}

map<pair<int, int>, int> mem;

int get(int x, int y) {
    x = abs(x);
    y = abs(y);
    return gcd(x, y);
//    typedef typename map<pair<int, int>, int>::mapped_type V;
//    auto r = mem.insert({{x, y}, V()});
//    V &v=r.first->second;
//    if (r.second)
//        v = gcd(x, y);
//    return v;
}

long calc(long w, long h, long k) {
    long res = 0;
    vector<int> mem(h + 1);
    vector<int> t2(h + 1);
    vector<int> mem2(h + 1);
    for (long b = 1; b < w; b++) {
        for (long c = 1; c < h && c * w <= 2 * (k + w); c++) {
            int mm = get(c, b);
//            c * w + (a - c) * b <= 2k;
            long mina = max((2 * k - c * w) / b + c, c);
            mina = min(mina, h);
            if (mina > c) {
                res += (mina - c) * 2 - 1;
            }
            for (long a = mina; a < h && c * w + (a - c) * b <= 2 * (k + w); a++) {
                long s = c * w + (a - c) * b;
                if (s / 2 <= k) {
                    res++;
                    if (a != c) res++;
                    continue;
                }
                long g = mm;
                if ((s - g + 2) / 2 <= k) {
                    res++;
                    if (a != c) res++;
                    continue;
                }
                if (t2[a] != b) {
                    t2[a] = b;
                    mem2[a] = get(a, w - b);
                }
                g += mem2[a];
                if ((s - g + 2) / 2 <= k) {
                    res++;
                    if (a != c) res++;
                    continue;
                }
                if (mem[a - c] == 0) {
                    mem[a - c] = get(a - c, w);
                }
                g += mem[a - c];
                if ((s - g + 2) / 2 <= k) {
                    res++;
                    if (a != c) res++;
                    continue;
                }
            }
        }
    }
    return res;
}

int main() {
    ios::sync_with_stdio(false);

    int w, h, k;
    cin >> w >> h >> k;
    auto start = std::chrono::high_resolution_clock::now();
    cout << (calc(w, h, k) + calc(h, w, k)) * 2;
    auto finish = std::chrono::high_resolution_clock::now();

    std::chrono::duration<double> elapsed = finish - start;
    cerr << elapsed.count() << "\n";

    return 0;
}
