「卡卡跑丁車」是一款最新型的賽車遊戲，由超可愛的角色、超酷炫的跑丁車陪你一起軋車甩尾，操作簡單容易上手，輕鬆休閒不麻煩！你只要在遊戲中，使用小技巧陷害對手，讓自己在時間內跑完全程，就可以獲得勝利唷！

在遊戲中遇到彎道時，通常需要減速以求安全過彎，而跑丁車提供了另一個選擇—甩尾！！雖然甩尾會使過彎速度下降，但累積三次甩尾後便可換取一個加速器，可以大幅縮減通過直線的時間！！可惜的是，當你囤積了兩個未使用的加速器後，再次甩尾並不會被累積計算。

卡卡是一名跑丁車玩家，由於缺乏經驗經常拿不到第一名。他最大的問題就是不清楚應該何時甩尾與使用加速器。他請你寫一個程式來提醒他在正確的地點做正確的事。

神奇的是卡卡平常通過任何彎道都需要 5 單位時間，若甩尾過彎則需平常的兩倍，也就是 10 單位時間。對於直線賽道來說，每通過 1 單位長度需要 2 單位的時間，若使用加速器則所需時間減半。

當然卡卡只會在彎道甩尾、直線使用加速器，並且一個彎道只能甩尾一次、一個加速器僅作用於一條直線賽道。

測資包含多組測試資料，第一列有一個整數 T 表示接下來有幾組測試資料。

每組測試資料表示一場競賽的全程路線，其第一列有一個整數 N，代表接下來有幾條直線賽道，相鄰兩個直線賽道間恰有一個彎道。下一列有 N 個非負整數，依序給出了每條直線賽道的長度。起點為第一條直線的首端，終點為最後一條直線的末端，賽道的總長度不會超過 2³¹-1 (1 <= N <= 10000)。

對每筆測試資料輸出卡卡到達終點所需的最短時間。

2
5
10 10 10 10 10
5
10 10 10 40 10

120
155

NPSC 2010 高中組初賽 (管理員：sagit)