import Data.Array
import System.IO
 
newRecord :: Int -> Int
newRecord n = maximum $ [score 1 a (b-a) (n-b) n | b <- [0..n], a <- h b]
  where
    gk = firstTimeWeCanGet ! (recordUpTo ! (n-1))
    h b = let top = min b (n-b) in
          if   n-gk < b-n+gk && n-gk < top
          then [0..n-gk] ++ [b-n+gk..top]
          else [0..top]

score acc 0 0 0 0 = acc
score acc a b c d = score (acc+1) (abs $ a-b) (abs $ b-c) (abs $ c-d) (abs $ d-a)

recordUpTo :: Array Int Int
recordUpTo = array (0,2^16-1) $ (0,0) : [(n, h n) | n <- [1..2^16-1]]
  where
    h n = max (newRecord n) (recordUpTo ! (n-1))
 
firstTimeWeCanGet :: Array Int Int
firstTimeWeCanGet = array (0,28) [(k, fst $ head $ dropWhile ((<k) . snd) $ assocs recordUpTo) | k <- [0..28]]
 
main = do
  hSetBuffering stdout NoBuffering
  mapM_ print $ assocs firstTimeWeCanGet