Q-31

T=int(input())
for tc in range(T):
    n,m=map(int,input().split())
    array=list(map(int,input().split()))
    dp=[]
    index=0
    for i in range(n):
        dp.append(array[index:index+m])
        index+=m
    for j in range(1,m): #순서*
        for i in range(n):
            if i==0:
                left_up=0
            else:
                left_up=dp[i][j]+dp[i-1][j-1]
            left=dp[i][j]+dp[i][j-1]
            if i==n-1:
                left_down=0
            else:
                left_down=dp[i][j]+dp[i+1][j-1]
            dp[i][j]=max(left,left_down,left_up)
    result=0
    for i in range(n):
        result=max(result,dp[i][m-1])
    print(result)