import Data.List
import Data.Maybe
import qualified Data.ByteString.Char8 as B
import qualified Data.Vector as V
main = mapM_ (print . solve) . analyze . map readInt . B.lines =<< B.getContents
readInt = fst . fromJust . B.readInt
analyze [] = []
analyze (n:cs) = (n,as):analyze bs where (as,bs) = splitAt (n-1) cs
solve (n,as) = dfs 0 where
  g = V.accum (flip (:)) (V.replicate n []) . flip zip [1..] . map pred $ as
  dfs i = maximum . (0:) . zipWith (+) [1..] . reverse . sort . map dfs $ g V.! i