# Arup Guha
# 2/13/2026
# Stick Splitting (for COP 4516 Team Contest #3 2026)

# Returns the best answre for items[lowIdx..highIdx]
def go(items, lowIdx, highIdx, dp):

    # Nothing to cut.
    if lowIdx+1 >= highIdx:
        return 0

    # Did this before.
    if dp[lowIdx][highIdx] != -1:
        return dp[lowIdx][highIdx]

    # Combine cost.
    add = items[highIdx]-items[lowIdx]

    # Can't be worse than this.
    cost = 100000000

    # Try each cut.
    for s in range(lowIdx+1, highIdx):
        tmp = go(items, lowIdx, s, dp) + go(items, s, highIdx, dp) + add
        cost = min(cost, tmp)

    # Store and return.
    dp[lowIdx][highIdx] = cost
    return cost

# Process cases.
nC = int(input())
for loop in range(nC):

    # Get marks.
    n = int(input())
    marks = [int(x) for x in input().split()]
    marks.append(n)
    newlist = marks[1:]
    newlist.insert(0, 0)

    # Init DP array.
    sz = len(newlist)
    dp = []
    for i in range(sz):
        tmp = []
        for j in range(sz):
            tmp.append(-1)
        dp.append(tmp)

    # Solve it!
    print(go(newlist, 0, len(newlist)-1, dp))