难度调整

Problem Description

比赛开始的前一晚，组题人终于敲定了所用的 $n$ 道题目。为了确保各个水平段的选手都有良好的参赛体验，组题人希望题目的难度系数连续：设题单中出现的最大难度系数为 $M$ ，则各题目的难度系数需要覆盖 $1 \sim M$ 的所有数字。(所有难度系数都是正整数) 然而由于各出题人的群魔乱舞，每道题目的实际难度系数只能保证在 $[1,10^9]$ 的区间内，而整体的分布并不乐观……想加题已经来不及了, 组题人只能以尽可能小的幅度对难度系数进行调整: 设题单中第 $i$ 题的实际难度系数为 $a_i$ ,调整后所标的难度系数为 $b_i$ , 组题人希望 $b$ 能满足以上要求，且最小化 $Ans=\sum_{i=1}^n |b_i-a_i|$。 然而组题人本人并不算聪明，这个问题对Ta还是太难了。请你帮他求出满足要求所需的最小调整幅度。

Input

第一行含一个正整数 $t ~(1 \leq t \leq 2 \times 10^5)$ ，表示共有多少组询问; 接下来 $t$ 组询问，每组将占两行:

• 第一行含一个正整数 $n ~ (1 \leq n \leq 10^6)$，表示题库内的题目数；
• 第二行含 $n$ 个正整数 $ a_{1 \sim 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$ 。

Output

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

Sample Input

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

Sample Output

1
4
11
12
2999999994

Source

2025“钉耙编程”中国大学生算法设计暑期联赛（3）