현자가 $H \times W$ 격자 형태의 사원에 들어왔습니다. 사원의 각 칸에는 현자의 돌이 놓여 있습니다. 현자는 첫 번째 행의 어느 열에서든 출발할 수 있으며, 한 행씩 내려가 마지막 행까지 도달하고자 합니다.
어떤 칸 $(r, c)$에 위치할 때, 다음 단계에서는 바로 아래 칸 $(r+1, c)$, 또는 왼쪽 아래 대각선 칸 $(r+1, c-1)$, 또는 오른쪽 아래 대각선 칸 $(r+1, c+1)$으로만 이동할 수 있습니다. (격자 밖으로는 나갈 수 없습니다.)

현자가 첫 번째 행에서 마지막 행까지 이동하면서 주울 수 있는 현자의 돌의 최대 개수를 구하는 프로그램을 작성하시오.



[제약 조건]
• 테스트 케이스 수 $T$
• $1 \le H, W \le 100$
• 각 칸의 돌 개수: $0 \le \text{돌 개수} \le 100$

첫째 줄에 테스트 케이스의 개수 $T$가 주어집니다.
각 테스트 케이스의 첫째 줄에는 격자의 세로 크기 $H$와 가로 크기 $W$가 공백으로 구분되어 주어집니다. ($1 \le H, W \le 100$)
다음 $H$개의 줄에 걸쳐 격자의 각 행에 놓인 돌의 개수가 각 열마다 공백으로 구분되어 주어집니다. 각 칸의 돌의 개수는 $0$ 이상 $100$ 이하의 정수입니다.

각 테스트 케이스마다 주울 수 있는 현자의 돌의 최대 개수를 한 줄에 하나씩 출력합니다.

1
6 5
3 1 7 4 2
2 1 3 1 1
1 2 2 1 8
2 2 1 5 3
2 1 4 4 4
5 2 7 5 1

32