比赛开始的前一晚，组题人终于敲定了所用的 $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 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 $，独占一行。