bool min2(int num,int turn);
bool max2(int num,int turn);



 int maxPath [25];
 int minPath [25];


bool min2(int num,int turn)
{
	if(num== 1)
	{
//cout << num <<" min picks last 1 and loses "<<endl<<endl;
		return false;
	}

	
	if(max2(num-1,turn+1)==false)
		{
minPath[turn]=1;
//cout << num <<" min picks  1 "<<endl;


		return true;
		}

 if(max2(num-2,turn+1)==false)
		{
minPath[turn]=2;
//cout << num <<" min picks  2 "<<endl;

		return true;
		}

	 if(max2(num-3,turn)==false)
		{
minPath[turn]=3;
//cout << num <<" min picks  3 "<<endl;

		return true;
		}
//	cout << num <<" nnnnnnnnnnnnnnnnnnnn2 "<<endl;

minPath[turn]=1;
//cout << num <<" min picks  1 "<<endl;
return false;
}





bool max2(int num, int turn)
{
	if(num==1)
	{
//cout << num <<" max picks last 1 and loses "<<endl<<endl;
		return false;
	}

	
	
		if(min2(num-1,turn+1)==false)
		{
maxPath[turn]=1;
//cout << num <<" max picks  1 "<<endl;
		return true;
		}

 if(min2(num-2,turn+1)==false)
		{
maxPath[turn]=2;
//cout << num <<" max picks  2 "<<endl;
		return true;
		}

		 if(min2(num-3,turn+1)==false)
		{
maxPath[turn]=3;
//cout << num <<" max picks  3 "<<endl;
		return true;
		}
	//cout << num <<" nnnnnnnnnnnnnnnnnnnn "<<endl;

maxPath[turn]=1;
//cout << num <<" max picks  1 "<<endl;

return false;
}

int nimAI(int n)
{
max2(n,0);
return maxPath[0];
}