{- Author: Robin Nittka -}
{-# OPTIONS_GHC -O2 #-}

module Main
	where

import System.IO
import Data.List
import Data.Array

remainders :: [Integer] -> Array (Int,Int) Integer
remainders list = array ((0,0),(len,len)) [ ((i,j), sum $ take (j-i) $ drop i list) | i <- [0..len], j <- [i..len] ]
	where len = length list

calcCol :: Int -> Array (Int,Int) Integer -> Int -> [Integer]
calcCol len rem 1 = [ toInteger (i+1) * (rem ! (0,i)) | i <- [1..len] ]
calcCol len rem c = map cost $ tail $ zip [0..] $ inits $ calcCol len rem (c-1)
	where cost (n,list) = minimum $ map ( \(m,v) -> v + (toInteger $ c+n) * rem ! (m,n) ) $ zip [1..] list

solve :: [Integer] -> Integer
solve input = last $ calcCol len (remainders input) len
	where len = length input

main :: IO ()
main = openFile "elias.in" ReadMode >>= hGetContents >>= mapM_ (print . solve . map read . words) . every2nd . lines
	where every2nd = map snd . filter (even . fst) . zip [1..]
