问题描述

有一个容量为 $A$ 升的杯子和一个容量为 $B$ 升的杯子。

从两个杯子都是空的状态开始，通过以下操作之一重复执行，直到其中一个杯子里的水达到 $C$ 升的状态：

• 将其中一个杯子装满水。
• 将其中一个杯子倒空。
• 将一个杯子 $X$ 的水无溢出地倒到另一个杯子 $Y$ 直到 $Y$ 满或 $X$ 空为止。

给定 $A, B$ 和 $K$，求在 $K$ 次操作内可以实现的不同的 $C$ 的数量。

输入

输入通过标准输入给出，其格式如下:

$A$ $B$ $K$

• 第1行是两个整数 $A$ 和 $B$，表示杯子的容量 $(1≦A,B≦10^{10})$。
• 第2行是一个整数 $K$，表示可以进行的操作次数 $(0≦K≦10^{10})$。

输出

输出实现的不同的 $C$ 的数量。最后要换行。

示例1

输入示例1

3 4 2

输出示例1

4

首先，初始状态下可以实现 $C=0$。

对于容量为 $3$ 和 $4$ 的杯子，分别用一次操作可以得到 $C=3$ 和 $C=4$。

对于 $C=1$，可以将 $4$ 升杯子中的水倒入 $3$ 升杯子中，需要两次操作。

不能在 $2$ 次操作内实现 $C=2$，而需要 $4$ 次操作。

示例2

输入示例2

7 3 0

输出示例2

1

由于没有操作次数，只能实现空状态（即 $C=0$）。

示例3

输入示例3

174324 96581 5000

输出示例3

3220