C. Удаление двух элементов
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Монокарпа есть массив целых чисел $$$a$$$, состоящий из $$$n$$$ элементов. Обозначим среднее арифметическое всех элементов массива за $$$k$$$ (обратите внимание, что $$$k$$$ может быть вещественным числом).

Среднее арифметическое массива из $$$n$$$ элементов — это сумма всех элементов массива деленная на $$$n$$$, то есть на количество элементов массива.

Монокарп решил удалить из массива $$$a$$$ ровно два элемента, при этом он хочет, чтобы после удаления среднее арифметическое оставшихся $$$(n - 2)$$$ элементов массива по-прежнему было равно $$$k$$$.

Перед вами стоит задача определить количество пар позиций $$$[i, j]$$$ ($$$i < j$$$) таких, что если удалить элементы из этих позиций, среднее арифметическое оставшихся $$$(n - 2)$$$ элементов массива будет равно $$$k$$$, то есть будет равно среднему арифметическому $$$n$$$ элементов изначального массива $$$a$$$.

Входные данные

Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных.

Первая строка каждого набора содержит одно целое число $$$n$$$ ($$$3 \le n \le 2 \cdot 10^5$$$) — количество элементов в массиве Монокарпа.

Во второй строке следует последовательность целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le 10^{9}$$$), где $$$a_i$$$ равно $$$i$$$-му элементу массива Монокарпа.

Сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

Выходные данные

Выведите количество пар позиций $$$[i, j]$$$ ($$$i < j$$$) таких, что если удалить элементы из этих позиций, среднее арифметическое оставшихся $$$(n - 2)$$$ элементов массива будет равно $$$k$$$, то есть будет равно среднему арифметическому $$$n$$$ элементов изначального массива $$$a$$$.

Пример
Входные данные
4
4
8 8 8 8
3
50 20 10
5
1 4 7 3 5
7
1 2 3 4 5 6 7
Выходные данные
6
0
2
3
Примечание

В первом примере можно удалить любую пару чисел, так как все элементы массива одинаковы.

Во второй примере нельзя удалить ни одной пары чисел таким образом, чтобы среднее арифметическое не изменилось.

В третьем примере можно удалить пару элементов в позициях $$$1$$$ и $$$3$$$ или пару элементов в позициях $$$4$$$ и $$$5$$$.