小明梦想穿越沙漠，沙漠中水资源很匮乏。小明需要依靠水站的支持，才能穿越整个沙漠。假设所有的水站都在一条直线上，而且小明沿着这条直线走。起点在1号水站，终点在第N号水站，起点和终点之间有若干个水站，按照到起点的距离从近到远编号。小明有个存储水的袋子，当小明走到水站时，水袋子就能被灌满。一单位的距离会消耗一个单位的水，现在小明想请你帮忙，计算出水袋子最小的容量V，以确保顺利完成旅途。途中一旦水袋中没有水，而且当前坐标又不是水站，就会发生危险。
第一行一个正整数 T 表示一共有多少组数据
对于每一组数据：
第一行一个正整数N，表示水站的个数（2<=N<=100000）
接下来N个整数表示，从1-N号水站的坐标X，（X<1000000000）
对于每组数据，输出一行为小明能顺利到达终点所需要水袋子的最小容量V。
1
6
1 2 3 4 5 61