Let's assume that we have a pair of numbers (*a*, *b*). We can get a new pair (*a* + *b*, *b*) or (*a*, *a* + *b*) from the given pair in a single step.

Let the initial pair of numbers be (1,1). Your task is to find number *k*, that is, the least number of steps needed to transform (1,1) into the pair where at least one number equals *n*.
The input contains the only integer *n* (1 ≤ *n* ≤ 10<sup class="upper-index">6</sup>).
5
3
1
0
2
1
3
2
4
3
10
5
1009
15
2009
17
7009
19
9009
20
19009
21
29009
22
12434
21
342342
28
342235
28
362235
28
762235
30
878235
30
978235
30
1000000
30
6
5
10000
20
999999
30
524287
29
777777
30
123756
26
976438
30
434563
28
345634
28
65457
24
123456
26
999997
30
98989
25
8
4
123455
26
990001
30
123141
26
998
16
453422
28
623423
29
89
9
24234
23
999879
30
345612
28
998756
30
999989
30
999998
30
999912
30
100000
25
#include<bits/stdc++.h>
using namespace std;
#define ll long long 
#define f(i,n) for(ll i=0;i<n;i++)
#define f1(i,n) for(ll i=n;i>=0;i--)
#define forr(i,a,b) for(ll i=a;i<b;i++)
#define forr1(i,a,b) for(ll i=a;i>=a;i--)
#define sor(vec) sort(vec.begin(),vec.end())
#define vl vector<ll>
#define pb push_back
#define so(arr,n) sort(arr,arr+n) 
const ll M = 998244353;

int main()
{
    int n;
    cin>>n;
    if(n==1)
      cout<<0;
   else
   {
      if(n%2==0)
      {
         cout<<n-1;
      }
      else
         cout<<(n-1)/2+1;
   }
    
}
   
   
      
   