CF1538B Friends and Candies

Polycarp has $ n $ friends, the $ i $ -th of his friends has $ a_i $ candies. Polycarp's friends do not like when they have different numbers of candies. In other words they want all $ a_i $ to be the same. To solve this, Polycarp performs the following set of actions exactly once: - Polycarp chooses $ k $ ( $ 0 \le k \le n $ ) arbitrary friends (let's say he chooses friends with indices $ i_1, i_2, \ldots, i_k $ ); - Polycarp distributes their $ a_{i_1} + a_{i_2} + \ldots + a_{i_k} $ candies among all $ n $ friends. During distribution for each of $ a_{i_1} + a_{i_2} + \ldots + a_{i_k} $ candies he chooses new owner. That can be any of $ n $ friends. Note, that any candy can be given to the person, who has owned that candy before the distribution process. Note that the number $ k $ is not fixed in advance and can be arbitrary. Your task is to find the minimum value of $ k $ . For example, if $ n=4 $ and $ a=[4, 5, 2, 5] $ , then Polycarp could make the following distribution of the candies: - Polycarp chooses $ k=2 $ friends with indices $ i=[2, 4] $ and distributes $ a_2 + a_4 = 10 $ candies to make $ a=[4, 4, 4, 4] $ (two candies go to person $ 3 $ ). Note that in this example Polycarp cannot choose $ k=1 $ friend so that he can redistribute candies so that in the end all $ a_i $ are equal. For the data $ n $ and $ a $ , determine the minimum value $ k $ . With this value $ k $ , Polycarp should be able to select $ k $ friends and redistribute their candies so that everyone will end up with the same number of candies.

The first line contains one integer $ t $ ( $ 1 \le t \le 10^4 $ ). Then $ t $ test cases follow. The first line of each test case contains one integer $ n $ ( $ 1 \le n \le 2 \cdot 10^5 $ ). The second line contains $ n $ integers $ a_1, a_2, \ldots, a_n $ ( $ 0 \le a_i \le 10^4 $ ). It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 2 \cdot 10^5 $ .

For each test case output: - the minimum value of $ k $ , such that Polycarp can choose exactly $ k $ friends so that he can redistribute the candies in the desired way; - "-1" if no such value $ k $ exists.