#!/usr/bin/php
<?php
 
    class GridHelper 
        {
        private $d1 = 1;
        private $d2 = 1;
        
        private $saved_paths = array();
        private $visited = array("1,1"=>true);
        private $path = "";        
        private $fail = 0;
         
        public function __tostring() 
        {
            return "GridHelper";
        }
    
        public function seek() 
        {
            while ($this->fail < 2000) 
        {
                $this->reset();
                $this->path();
        }
                return count($this->saved_paths);
        }
        
        public function path() 
	{
            $point = $this->getNextPoint();
            $point_as_string = join(",",$point);
            if ($point_as_string == "0,0") 
	    { 
                $this->fail += 1; 
                $this->path = "";
                return; 
            }
            if ($point_as_string == "4,4") 
	    { 
                if (!isset($this->saved_paths[$this->path])) 
		{
                    $this->saved_paths[$this->path] = $this->path;
                    $this->fail = 0;
                }
                $this->path = "";
                return; 
            }
            return $this->path();
        }
        
        public function reset() 
	{
            $this->d1 = 1;
            $this->d2 = 1;
            $this->visited = array("1,1"=>true);
        }
        
        
        private function getNextPoint() 
	{
            $x = array();
            
            if (($this->d1 != 1)&&
                (!isset($this->visited[join(",",array($this->d1 -1,$this->d2))]))) 
	      { 
                  array_push($x,array($this->d1 -1,$this->d2)); 
              }
            if (($this->d1 != 4)
                &&(!isset($this->visited[join(",",array($this->d1 +1,$this->d2))]))) 
	      { 
                  array_push($x,array($this->d1 +1,$this->d2)); 
              }
            if (($this->d2 != 1)
                &&(!isset($this->visited[join(",",array($this->d1,$this->d2 -1))]))) 
	      { 
                  array_push($x,array($this->d1,$this->d2 -1)); 
              }
            if (($this->d2 != 4)&&
	        (!isset($this->visited[join(",",array($this->d1,$this->d2 +1))])))
	      { 
                  array_push($x,array($this->d1,$this->d2 +1)); 
              }
 
            $l = count($x);
            $new_point_array = array(0,0); 
            if ($l > 0) 
	      {            
              	  shuffle($x);
           	  $new_point_array = $x[array_rand($x,1)];
          	  $this->d1 = $new_point_array[0];
            	  $this->d2 = $new_point_array[1];
           	  $new_point_array_as_string = join(",",$new_point_array);
          	  $this->visited[$new_point_array_as_string] = true;
               	  $this->path .= $new_point_array_as_string." ";
              } 
            return $new_point_array;
        }
    
    }
    
    $g = new GridHelper();
    print $g->seek()."\n";
 
    exit;
?>