配点 : $1000$ 点

問題文

$2$ 次元平面上に $(0,0)$, $(W,0)$, $(0,H)$, $(W,H)$ を頂点とするような長方形 $R$ があります。 $W$, $H$ は正の整数です。 このとき、次の条件をすべて満たすような $2$ 次元平面上の三角形 $\Delta$ の個数を求めてください。

• $\Delta$ の各頂点は格子点である。つまり、座標がいずれも整数である。
• $\Delta$ と $R$ は頂点を共有しない。
• $\Delta$ の各頂点は $R$ の周上にあり、それぞれが属する辺は相異なる。
• $\Delta$ の内部（周上及び頂点を含まない）にある格子点は高々 $K$ 個である。

制約

• $1 \leqq W \leqq 10^5$
• $1 \leqq H \leqq 10^5$
• $0 \leqq K \leqq 10^5$
• 入力で与えられる値はすべて整数である。

入力

入力は以下の形式で標準入力から与えられる。

$W$ $H$ $K$

出力

答えを出力せよ。

2 3 1

12

例えば $(1,0)$, $(0,2)$, $(2,2)$ を頂点とするような三角形は、 内部に格子点が $1$ つしか存在しないので、条件を満たします。

5 4 5

132

100 100 1000

461316