#include<bits/stdc++.h>
#define int long long
using namespace std;
long long t,n,m;
inline int read(){
register int a=0,b=1; register char ch=getchar();
while(ch<'0'||ch>'9')
b=(ch=='-')?-1:1,ch=getchar();
while(ch>='0'&&ch<='9')
a=(a<<3)+(a<<1)+(ch^48),ch=getchar();
return b==-1?-a:a;
}
template<typename T>inline void write(T x){
if(x<0)putchar('-'),x=-x;
if(x>=10)write(x/10);
putchar(x%10+'0');
}
signed main(){
t=20;//t=read();
while(t--){
n=1000000000,m=10000;//n=read(),m=read();
register long long now=1,ans=1,nxt;
while(now<=n){
--m,nxt=(now-ans)/m,++m;
if(now+nxt>=n){ans+=(n-now)*m;break;}
++nxt,now+=nxt,ans+=nxt*m,--ans,ans%=now,++ans,--nxt;
}
write(ans);putchar('\n');
}
return 0;
}