
fun main(args:Array<String>):Unit {
    repeat(readLine()!!.toInt()){
        val len = readLine()!!.trim().toInt()
        val ea = readLine()!!.trim().split(' ').map(String::toInt).toIntArray()
        val memo = Array(len){Array(len){-1}}
        println(search(ea, memo))
    }
}

fun search(ea:IntArray, memo:Array<Array<Int>>, last:Int = ea.size - 1, prev:Int = 0):Int {
    if (memo[last][prev] >= 0) return memo[last][prev]
    memo[last][prev] = when(last){
        0 -> if (prev == 0) ea.first() else 0
        1 -> when {
            ea.first() >= prev -> ea[1]
            else -> 0
        }
        else -> when{
            ea[last - 1] > prev -> {
                val res = search(ea, memo,last - 2, 0)
                ea[last] + res
            }
            ea[last - 1] == prev -> {
                val res = search(ea, memo,last - 2, 1)
                if (res > 0)
                    ea[last] + res - 1
                else
                    ea[last]
            }
            else -> {
                val res = search(ea, memo, last - 2, prev - ea[last - 1] + 1)
                when {
                    res > 0 -> ea[last] + res - 1
                    search(ea, memo, last - 2, prev - ea[last - 1]) > 0 -> ea[last]
                    else -> 0
                }
            }
        }
    }
    return memo[last][prev]
}
/*

F 最後を最大にする並び
->最後から一つ前が0ならばG-2
->最後から一つ前が0でなければF-2

Fp := 最後から一つ前がp以上で、最後が最大のもの
最後から一つ前l
-> p+1以上ならF-20
-> F-2p-l
 */
