小L老师老家的果园大丰收，于是乎小L老师准备拿一些水果来分配给同学们，但是由于苹果数量有限，小L老师
又想让每个同学都能得到苹果，然后成绩好的同学能分配到多一点的苹果。于是乎，小L老师制定了两个标准：
1.每个同学至少能分到一个苹果。
2.相邻的同学成绩高的分到的苹果数量更多。
聪明的你知道如何分配使得小L老师剩下的苹果数量更多嘛。
输入描述:
第一行一个整数T（1≤T≤500），表示共有T组测试数据。
对于每组测试数据，第一行一个整数n（1≤n≤10000）表示有n个同学，第二行有n个ai(1≤ai≤10000)表示每名同学的成绩
输出描述:
输出一个一个整数表示至少需要分配多少个苹果。
示例1
说明
样例二 :第一名同学至少需要分配1个苹果
第二名同学至少需要分配2个苹果
第三名同学至少需要分配3个苹果
所以一共至少需要分配6个苹果
备注: