Problem Description

There are two cups, one that can hold $ A $ liters of water and another that can hold $ B $ liters of water.

Starting from an empty state, we want to reach a state where one of the cups contains exactly $ C $ liters of water by repeatedly performing one of the following operations:

• Fill one of the cups to the brim with water.
• Empty one of the cups.
• Transfer water from one cup $ X $ to the other cup $ Y $ without spilling, until $ Y $ is full or $ X $ is empty.

Given $ A, B, K $, determine how many distinct values of $ C $ can be achieved within $ K $ operations.

Input Format

The input is given from the standard input in the following format:

$ A $ $ B $ $ K $

• The first line contains integers $A, B\ (1\ ≦\ A,\ B\ ≦\ 10^{10})$ representing the capacities of the cups, and an integer $K\ (0\ ≦\ K\ ≦\ 10^{10})$ representing the number of allowed operations.

Output Format

Determine how many distinct values of $ C $ can be achieved. Print the result followed by a newline.

Sample Input and Output

Sample Input #1

3 4 2

Sample Output #1

4

Sample Input #2

7 3 0

Sample Output #2

1

Sample Input #3

174324 96581 5000

Sample Output #3

3220

Notes/Hints

Sample Explanation 1

Initially, $ 0 $ is achieved. $ 3 $ and $ 4 $ can be achieved with one operation each by filling the respective cups. $ 1 $ can be achieved in two operations by filling the 4-liter cup and transferring its water to the empty 3-liter cup. $ 2 $ cannot be achieved in two operations and requires four operations.

Sample Explanation 2

Since no operations are possible, only the empty state, i.e., $ 0 $, can be achieved.

见题面 Input 部分

见题面 Output 部分