题目描述

有 $n$ 个盒子排列在一个圆环上，按照顺时针方向依次编号为 $1,2,\ldots,n$。

第 $i$ 个盒子中初始有 $a_i$ 个球，并保证所有盒子中的球数总和不超过盒子数，即

你需要重新分配这些球，使得最终每个盒子中最多只有一个球。

一次操作可以选择一个球，将它从当前盒子移动到相邻的一个盒子中。具体来说：

• 对于 $1\le i<n$，盒子 $i$ 与盒子 $i+1$ 相邻；
• 盒子 $1$ 与盒子 $n$ 相邻。

请计算完成重新分配所需的最少操作次数。

输入格式

第一行包含一个整数 $T$，表示测试用例的数量。

接下来依次输入 $T$ 组测试数据。对于每组测试数据：

• 第一行包含一个正整数 $n$，表示盒子的数量；
• 第二行包含 $n$ 个非负整数 $a_1,a_2,\ldots,a_n$，其中 $a_i$ 表示第 $i$ 个盒子中初始的球数。

输出格式

对于每组测试数据，输出一行一个非负整数，表示使每个盒子中最多只有一个球所需的最少操作次数。

样例

输入

1
12
0 0 2 4 3 1 0 0 0 0 0 1

输出

19

数据范围

对于所有测试数据：

同一个输入文件内所有测试用例的 $n$ 之和不超过 $6\times 10^5$。

答案可能超过 $32$ 位有符号整数的范围，请使用 $64$ 位整数保存答案。