#include<bits/stdc++.h>
using namespace std;
uint32_t x, y=1, z=2, w=3;
uint32_t generate() { 
	uint32_t t=(x^(x<<11));
	x=y;
	y=z;
	z=w;
	return w=(w^(w>>19))^(t^(t>>8));
}
const uint32_t d=3900000;
const uint32_t T=(1u<<31)-d;
int p,q[2*d];
main(){
	cin>>x;
	for(int i=0;i<10000001;++i){
		uint32_t a=generate();
		if(a<T){
			++p;
		}else if(a<T+2*d){
			++q[a-T];
		}
	}
	uint32_t i=T-1;
	for(;p<=5000000;){
		p+=q[++i-T];
	}
	cout<<i<<"\n";
}