from collections import deque
from collections import OrderedDict
import queue
import heapq
import math
import sys
sys.setrecursionlimit(10**6)
def sf(): return [int(x) for x in input().split(" ")]
def sfi(): return int(input())
def sfs(): return input()
def printf(x):
print(x)
sys.stdout.flush()
def main():
t = int(input())
for tc in range(t):
n = int(input())
dp = [0]*(n+5)
bosses = [int(x) for x in input().split(" ")]
bosses.append(0)
for i in range(n-1,-1,-1):
cost1 = bosses[i] + min(dp[i+2],dp[i+3])
cost2 = bosses[i] + bosses[i+1] + min(dp[i+3],dp[i+4])
dp[i] = min(cost1, cost2)
print(dp[0])
if __name__ == "__main__":
main()#include <bits/stdc++.h>
#define MOD 1000000007;
#define MOD2 998244353;
#define IM ll_MAX;
#define IN ll_MIN;
#define mp make_pair;
#define ff first;
#define ss second;
#define PI 3.14159265;
#define N1 1e6;
#define N2 1e14;
using namespace std;
typedef long long ll;
typedef long long int lli;
typedef long double lld;
typedef unsigned int ui;
void Om_Nav() {
ll npr;
cin >> npr;
vector<ll> nums(npr);
for(ll idx = 0;idx < npr;idx++) {
cin >> nums[idx];
}
vector<vector<ll>> DP;
DP.resize(npr, vector<ll>(2));
/*Base case*/
DP[0][1] = nums[0];
DP[0][0] = 2e9;
/*begin value boss*/
if(npr > 1) {
DP[1][0] = DP[0][1];
DP[1][1] = DP[0][1] + nums[1];
}
for(ll idx = 2;idx < npr;idx++) {
/*prev boss and prev to prev boss*/
DP[idx][0] = min(DP[idx-1][1], DP[idx-2][1]);
/*min of curr bosses and prev boss sequence*/
DP[idx][1] = min(DP[idx-1][0] + nums[idx], DP[idx-2][0] + nums[idx] + nums[idx-1]);
}
cout << min(DP[npr-1][0], DP[npr-1][1]) << "\n";
return;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
ll tpr;
cin >> tpr;
while(tpr--) {
Om_Nav();
}
return 0;
}1373C - Pluses and Minuses | 1173B - Nauuo and Chess |
318B - Strings of Power | 1625A - Ancient Civilization |
864A - Fair Game | 1663B - Mike's Sequence |
448A - Rewards | 1622A - Construct a Rectangle |
1620A - Equal or Not Equal | 1517A - Sum of 2050 |
620A - Professor GukiZ's Robot | 1342A - Road To Zero |
1520A - Do Not Be Distracted | 352A - Jeff and Digits |
1327A - Sum of Odd Integers | 1276A - As Simple as One and Two |
812C - Sagheer and Nubian Market | 272A - Dima and Friends |
1352C - K-th Not Divisible by n | 545C - Woodcutters |
1528B - Kavi on Pairing Duty | 339B - Xenia and Ringroad |
189A - Cut Ribbon | 1182A - Filling Shapes |
82A - Double Cola | 45A - Codecraft III |
1242A - Tile Painting | 1663E - Are You Safe |
1663D - Is it rated - 3 | 1311A - Add Odd or Subtract Even |