Давным-давно Берляндия была маленькой страной, в которой проживало только \(n\) человек. Каждый из них имел некоторое количество сбережений: у \(i\)-го человека было \(a_i\) бурлей.
Правительство считало человека богатым, если у него было хотя бы \(x\) бурлей. Чтобы увеличить количество богатых людей в Берляндии, решили провести несколько реформ. Каждая реформа выглядела следующим образом:
- правительство выбирает некоторое подмножество людей (возможно, всех);
- правительство забирает все сбережения у выбранных людей и перераспределяет их среди выбранных людей поровну.
Например, представим сбережения как список \([5, 1, 2, 1]\): если правительство выбирает \(1\)-го и \(3\)-го человека, то оно, сначала заберет у них все \(5 + 2 = 7\) бурлей, а потом вернет каждому по \(3.5\) бурлей. В результате сбережения примут вид \([3.5, 1, 3.5, 1]\).
Много информации было потеряно с того времени, поэтому мы не знаем, сколько реформ было проведено и на ком. Все, что мы можем — это попросить вас посчитать максимально возможное количество богатых людей после некоторого (возможно нулевого) количества реформ.
Выходные данные
Выведите \(T\) чисел — по одному на набор входных данных. Для каждого набора выведите максимально возможное количество богатых людей после некоторого (возможно нулевого) количества реформ.
Примечание
Первый пример описан в условии задачи.
Во втором примере правительство, например, могло провести следующие реформы: \([\underline{11}, \underline{9}, 11, 9] \rightarrow [10, 10, \underline{11}, \underline{9}] \rightarrow [10, 10, 10, 10]\).
В третьем примере правительство не сможет сделать даже одно человека богатым.
В четвертом примере правительство могло выбрать всех людей в реформе: \([\underline{9}, \underline{4}, \underline{9}] \rightarrow [7\frac{1}{3}, 7\frac{1}{3}, 7\frac{1}{3}]\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
4 3
5 1 2 1
4 10
11 9 11 9
2 5
4 3
3 7
9 4 9
|
2
4
0
3
|