import math

def maxStepValue(v):
    n = len(v)
    if n == 1:
        return v[0]
    if n == 2:
        return v[0] + math.ceil(v[1]/2)

    dp = [0 for _ in range(n)]
    dp[0], dp[1] = v[0], v[0] + math.ceil(v[1]/2)
    for i in range(2, n):
        dp[i] = max(dp[i-1] + math.ceil(v[i] / 2), dp[i-2] + v[i])

    return int(dp[-1])


if __name__=='__main__':
    samples = int(input())
    for _ in range(samples):
        n = input()
        v = input().split(' ')
        v = [int(each) for each in v]
        print(maxStepValue(v))
