Description

雷王最近沉迷上了战争类型的$RPG$游戏，但是即使在其他类型的游戏中，他也没有放弃扫雷，所以他选择扮演了一名排雷兵。
初始时他降落在了一条长度为$n$的战场上，每个位置的编号为$1，2，……，n$。某些位置下埋着地雷，如果雷王可以准确的知道哪些位置下埋着地雷，士官长就会给予他排雷达人勋章。现在雷王有一个有限制条件的雷达，只要花费$C_{i,j}$的电量，雷达就可以告知他$i，i+1，i+2，……，j - 1， j$位置下埋着的地雷总数的奇偶性，把这种操作称为一次对[$i,j$]的查询。（$1 \leq i \leq j \leq n$） 雷王想要知道至少需要花费多少电，才能保证知道哪些位置埋着地雷，你可以告诉他吗？

Input Format

在第一行中输入一个正整数$t$，代表测试用例的个数。（$1\leq t \leq 10$） 对于每组测试用例： 在第一行中输入一个正整数$n$，代表战场的长度。（$1 \leq n \leq 2e3$） 在接下来的第$i$行中($1 \leq i \leq n$)，输入$n - i + 1$ 个以空格隔开的正整数，表示不同的查询操作所需的花费。其中$C_{i,j}$（对区间$[i, j]$查询的费用，$1 \leq i \leq j \leq n$， $1 \leq C_{i,j} \leq 1e9$）为第$i$行第$j+1-i$​个数。 保证所有测试用例$n$的总和不超过$2e3$。

Output Format

在一行中输出一个正整数，表示在保证知道哪些位置埋着地雷的前提下，电量的最小花费。

1
5
14 24 20 7 18
48 19 87 39
98 79 21
31 16
77

76