19 年校赛的结果已经出炉，为了对大家的积极参与表示感谢，杨主席准备拿出他的工资给大家发福利。
所有参赛选手排成一排，每位同学都对于有一个量化的得分（当然，得分越高越好）。杨主席已事先知道选手们的排队顺序以及个人的得分，他将一个一个给大家发糖。
杨主席是个有原则的男人，但他原则也是有限的。所谓有原则是指：分数高的一定比分数低的能拿到更多的糖果且分数 一样的拿到的糖果一样多；所谓原则是有限的又是指：刚刚说的原则仅对排队中相邻的两人生效，且允许有人拿不到糖果（杨主席是个穷逼）。
杨主席并不想多花一分钱买额外的糖，于是他想知道在各种情况下最少需要购入几块糖。
首先是一个整数T，表示数据输入的组数，T<=20。
对于每组数据，有两行：
（1）一个整数n，表示队列中的人数，0 < n <= 1000。
（2）n个整数a[0] ... a[n-1]，表示按队列顺序每个人的得分，注意可能会有同分的情况，保证a[i]是int类型的。
对应T行，每行即对应每组输入的最少购入糖数结果。