数据组数较多，请注意常数优化。
sjy也开始玩泡泡龙了，但是稍微有点不一样 
sjy的泡泡龙游戏是一串积木(真是低级)，共n个。每块积木高度不同。
sjy的消积木法则是：他先选一串[l,r]之间的积木，如果这一串积木左右对称，如：1,3,2,3,1,就能用1点能量把这一串积木消掉。
sjy想知道，他最少需要多少点能量就能把所有积木消掉。

输入格式
第一行一个数t,表示有t组数据。
接下来t组数据，每组数据有两行，
第一行是n,表示n个积木，第二行n个数，表示n个积木的高度Hi。

输出格式
共t行，表示每次的最小能量值。
输入样例 复制
1
5
1 2 3 1 2
输出样例 复制
3
数据范围与提示
40%:==1,1≤n≤12,1≤Hi≤10
100%:1≤t≤10,1≤n≤500,1≤Hi≤100
样例：
先消1(左起第4个)
再消2 3 2 再消1