题目描述

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

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

输入格式

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

$W$ $H$ $K$

输出格式

答えを出力せよ。

2 3 1

12

5 4 5

132

100 100 1000

461316

提示

制約

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

Sample Explanation 1

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