#include <iostream>
#include <algorithm>
using namespace std;
uint32_t i,j,t,x,y=1,z=2,w=3,a[7500000];
main(){
	cin>>x;
	for(i=10000001;i--;){
		t=x^x<<11,x=y;y=z;z=w;w^=w>>19^t^t>>8; 
		w<3e9?a[j++]=w:0;
	}
	sort(a,a+j);
	cout << a[5000000] << endl;
}