比赛开始的前一晚，组题人终于敲定了所用的 $n$ 道题目。为了确保各个水平段的选手都有良好的参赛体验，组题人希望题目的难度系数连续：设题单中出现的最大难度系数为 $M$，则各题目的难度系数需要覆盖 $1 \sim M$ 的所有数字。(所有难度系数都是正整数)

然而由于各出题人的群魔乱舞，每道题目的实际难度系数只能保证在 $[1,10^9]$ 的区间内，而整体的分布并不乐观……想加题已经来不及了，组题人只能以尽可能小的幅度对难度系数进行调整：

设题单中第 $i$ 题的实际难度系数为 $a_i$，调整后所标的难度系数为 $b_i$，组题人希望 $b$ 能满足以上要求，且最小化 $Ans=\sum_{i=1}^n |b_i-a_i|$。

然而组题人本人并不算聪明，这个问题对 Ta 还是太难了。请你帮他求出满足要求所需的最小调整幅度。

输入格式

第一行含一个正整数 $t$ $(1 \leq t \leq 2 \times 10^5)$，表示共有多少组询问;

接下来 $t$ 组询问，每组将占两行:

第一行含一个正整数 $n$ $(1 \leq n \leq 10^6)$，表示题库内的题目数；
第二行含 $n$ 个正整数 $a_1 \sim a_n$ $(1 \leq a_i \leq 10^9; \forall 1 \leq i < n, a_i \leq a_{i+1})$，$a_i$ 表示第 $i$ 题的实际难度系数。

保证 $n>10^5$ 的数据不超过 1 组，$n>10^4$ 的数据不超过 11 组；保证 $\sum n \leq 4 \times 10^6$。

输出格式

对每组询问，输出一个非负整数 $Ans$，独占一行。

样例

输入

5
5
1 2 2 4 4
8
1 1 1 1 5 5 5 5
11
1 1 4 4 8 8 8 8 8 8 12
11
1 1 4 4 8 8 8 8 8 12 12
3
1000000000 1000000000 1000000000

输出

1
4
11
12
2999999994