# Monks CodeChef Solution

### We Are Discuss About CODECHEF SOLUTION

Monks CodeChef Solution

## Monks CodeChef Solution

There is a town with N people and initially, the i^{th} person has A_i coins. However, some people of the town decide to become monks. If the i^{th} person becomes a monk, then:

• He leaves the town thereby reducing the number of people in the town by 1.
• He distributes X (0 \le X \le A_i) coins to the remaining people of the town (not necessarily equally). Note that each monk can freely choose his value of X, and different monks may choose different values of X.
• He takes the remaining A_i – X coins with him.

For example, initially, if A = [1, 3, 4, 5] and 4^{th} person decides to become a monk then he can leave the town and can give 2 coins to the 1^{st} person, 1 coin to the 2^{nd} person, no coins to the 3^{rd} person and take 2 coins along with him while going. Now A becomes [3, 4, 4].

Determine the minimum number of people who have to become monks, so that in the end, everyone remaining in the town has an equal number of coins.

### Input Format

• The first line contains a single integer T — the number of test cases. Then the test cases follow.
• The first line of each test case contains an integer N — the number of people in the town.
• The second line of each test case contains N space-separated integers A_1, A_2, \ldots, A_N denoting the initial number of coins of everyone in the town.

### Output Format

For each test case, output the minimum number of people who have to become monks, so that in the end, everyone remaining in the town has an equal number of coins.

### Constraints

• 1 \le T \le 10^5
• 1 \le N \le 10^5
• 1 \le A_i \le 10^9
• Sum of N over all test cases does not exceed 2 \cdot 10^5.

### Sample 1:

Input

Output

3
4
6 6 6 6
3
5 1 4
5
2 1 2 1 1

0
1
2


### Explanation:

Test case 1: All the people already have an equal number of coins.

Test case 2: The 2^{nd} person can become a monk and give his 1 coin to the person with 4 coins. After this, both the remaining people will have 5 coins.

Test case 3: One way of two people becoming monks is as follows:

• The 2^{nd} person becomes a monk, and takes his 1 coin with him
• The 3^{rd} person becomes a monk, and gives one coin each to the 4^{th} and 5^{th} people

Everyone remaining in the town now has 2 coins.

## SOLUTION

Yhaa You have done it but next? if YOU Want to Get Others Please Visit Here ScishowEngineer   Then Follow US HERE and Join Telegram.