Zhan, tired after the contest, gave the only task that he did not solve during the contest to his friend, Sungat. However, he could not solve it either, so we ask you to try to solve this problem.

You are given an array $a_1, a_2, \ldots, a_n$ of length $n$. We can perform any number (possibly, zero) of operations on the array.

In one operation, we choose a position $i$ ($1 \leq i \leq n - 1$) and perform the following action:

• $a_i := a_i - 1$, and $a_{i+1} := a_{i+1} + 1$.

Find the minimum possible value of $\max(a_1, a_2, \ldots, a_n) - \min(a_1, a_2, \ldots, a_n)$.

Input

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^5$). The description of the test cases follows.

The first line of each test case contains an integer $n$ ($1 \leq n \leq 2 \cdot 10^5$).

The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \leq a_i \leq 10^{12}$).

The sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.

Output

For each test case, output a single integer: the minimum possible value of $\max(a_1, a_2, \ldots, a_n) - \min(a_1, a_2, \ldots, a_n)$.

Note

In the third testcase, you can perform the operation twice with $i = 1$.

After that, the array is $a = [2, 3, 2, 3]$, and $\max(2, 3, 2, 3) - \min(2, 3, 2, 3) = 3 - 2 = 1$.