C+=

Source: Codeforces

Version: Phuoc Hung OJ Extended

Problem Statement

Given positive integers $a,b$ and $n$ with $a,b\le n$, in one operation choose a += b or b += a. Find the minimum operations until at least one value becomes strictly greater than $n$. The optimal strategy always adds the larger number into the smaller one. This edition reads one triple, not a leading test count.

Input

A line contains exactly three integers $a,b,n$ with $1\le a,b\le n\le10^9$. This PHOJ edition reads one triple, with no leading $t$.

Output

Print the minimum number of operations.

Subtasks

• Subtask 1 (20%): $1\le a,b\le n\le 20$.

• Subtask 2 (30%): $1\le a,b\le n\le 100000$.

• Subtask 3 (50%): $1\le a,b\le n\le 1000000000$.

Examples

Example 1

Input:

1 2 3

Output:

2

Explanation:

Limit n=3. States (a,b) after operations: 1: (3,2); 2: (3,5). First exceedance occurs after 2 operations.

Example 2

Input:

5 4 100

Output:

7

Explanation:

Limit n=100. States (a,b) after operations: 1: (5,9); 2: (14,9); 3: (14,23); 4: (37,23); 5: (37,60); 6: (97,60); 7: (97,157). First exceedance occurs after 7 operations.