Polycarp got an array of integers a[1…n]a[1…n] as a gift. Now he wants to perform a certain number of operations (possibly zero) so that all elements of the array become the same (that is, to become a1=a2=⋯=ana1=a2=⋯=an). In one operation, he can take some indices in the array and increase the elements of the array at those indices by 11. For example, let a=[4,2,1,6,2]a=[4,2,1,6,2]. He can perform the following operation: select indices 1, 2, and 4 and increase elements of the array in those indices by 11. As a result, in one operation, he can get a new state of the array a=[5,3,1,7,2]a=[5,3,1,7,2]. What is the minimum number of operations it can take so that all elements of the array become equal to each other (that is, to become a1=a2=⋯=ana1=a2=⋯=an)?

Plus One on the Subset solution codeforces

Polycarp got an array of integers a[1n]a[1…n] as a gift. Now he wants to perform a certain number of operations (possibly zero) so that all elements of the array become the same (that is, to become a1=a2==ana1=a2=⋯=an).

  • In one operation, he can take some indices in the array and increase the elements of the array at those indices by 11.

For example, let a=[4,2,1,6,2]a=[4,2,1,6,2]. He can perform the following operation: select indices 1, 2, and 4 and increase elements of the array in those indices by 11. As a result, in one operation, he can get a new state of the array a=[5,3,1,7,2]a=[5,3,1,7,2].

What is the minimum number of operations it can take so that all elements of the array become equal to each other (that is, to become a1=a2==ana1=a2=⋯=an)?

Input Plus One on the Subset solution codeforces

The first line of the input contains a single integer tt (1t1041≤t≤104)  — the number of test cases in the test.

The following are descriptions of the input test cases.

The first line of the description of each test case contains one integer nn (1n501≤n≤50)  — the array aa.

The second line of the description of each test case contains nn integers a1,a2,,ana1,a2,…,an (1ai1091≤ai≤109)  — elements of the array aa.

Output Plus One on the Subset solution codeforces

For each test case, print one integer  — the minimum number of operations to make all elements of the array aa equal.

Example

input

Copy
3
6
3 4 2 4 1 2
3
1000 1002 998
2
12 11

output Plus One on the Subset solution codeforces

Copy
3
4
1
Note

First test case:

  • a=[3,4,2,4,1,2]a=[3,4,2,4,1,2] take a3,a5a3,a5 and perform an operation plus one on them, as a result we get a=[3,4,3,4,2,2]a=[3,4,3,4,2,2].
  • a=[3,4,3,4,2,2]a=[3,4,3,4,2,2] we take a1,a5,a6a1,a5,a6 and perform an operation on them plus one, as a result we get a=[4,4,3,4,3,3]a=[4,4,3,4,3,3].
  • a=[4,4,3,4,3,3]a=[4,4,3,4,3,3] we take a3,a5,a6a3,a5,a6 and perform an operation on them plus one, as a result we get a=[4,4,4,4,4,4]a=[4,4,4,4,4,4].

There are other sequences of 33 operations, after the application of which all elements become equal.

Second test case: Plus One on the Subset solution codeforces

  • a=[1000,1002,998]a=[1000,1002,998] 2 times we take a1,a3a1,a3 and perform an operation plus one on them, as a result we get a=[1002,1002,1000]a=[1002,1002,1000].
  • a=[1002,1002,1000]a=[1002,1002,1000] also take a3a3 2 times and perform an operation plus one on it, as a result we get a=[1002,1002,1002]a=[1002,1002,1002].

Third test case:

  • a=[12,11]a=[12,11] take a2a2 and perform an operation plus one on it, as a result we get a=[12,12]a=[12,12].
  • For Solution

    Click Here!

Leave a Comment

Your email address will not be published.