問題文

水が $A$ リットル入るカップと、水が $B$ リットル入るカップが $1$ つずつあります。

カップが空の状態から始めて、次のいずれかの操作を繰り返し行うことにより、いずれかのカップに水が $C$ リットルたまる状態にしたいです。

• 一方のカップを水でいっぱいにする。
• 一方のカップを空にする。
• 一方のカップ $X$ からもう一方のカップ $Y$ に、 $Y$ がいっぱいになるか $X$ が空になるまで、水をこぼさずにうつす。

$A, B, K$ が与えられるので、 $K$ 回以内の操作で実現できる相異なる $C$ は何通りあるかを求めなさい。

入力

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

$A$ $B$ $K$

• $1$ 行目には，カップの容量を表す整数 $A,B (1 ≦ A, B ≦ 10^{10})$ と、操作可能な回数を表す整数 $K (0 ≦ K ≦ 10^{10})$ が与えられる。

出力

実現できる相異なる $C$ は何通りあるかを求めよ。出力の最後には改行を入れること。

入力例1

3 4 2

出力例1

4

まず、 $0$ は初期状態で実現されています。

$3$ および $4$ は、それぞれの容量のカップの水を満たす、 $1$ 回の操作で達成可能です。

$1$ は、 容量 $4$ のカップに入れた水を、空になっている容量 $3$ のカップに移す、$2$ 回の操作で実現できます。

$2$ は、$2$ 回の操作で実現することは出来ず、 $4$ 回の操作が必要となります。

入力例2

7 3 0

出力例2

1

操作不可能なので、空の状態、つまり $0$ のみを実現することしかできません。

入力例3

174324 96581 5000

出力例3

3220