D. Ярик и ноты
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Ярик — большой фанат разной музыки. Но Ярик любит не только слушать музыку, но и писать её. Больше всего он любит электронную музыку, поэтому он придумал свою собственную систему нот, которая, по его мнению, лучше всего подходит для неё.

Так как Ярик ещё и увлекается информатикой, то в его системе ноты обозначаются числами вида $$$2^k$$$, где $$$k \ge 1$$$ — целое положительное число. Но, как известно, просто нотами для написания музыки не обойтись, поэтому Ярик использует сочетания из двух нот. Сочетание двух нот $$$(a, b)$$$, где $$$a = 2^k$$$ и $$$b = 2^l$$$, он обозначает числом $$$a^b$$$.

Например, если $$$a = 8 = 2^3$$$, $$$b = 4 = 2^2$$$, то сочетание $$$(a, b)$$$ обозначается числом $$$a^b = 8^4 = 4096$$$. Обратите внимание, что разные сочетания могут иметь одинаковое обозначение, например сочетание $$$(64, 2)$$$ тоже обозначается числом $$$4096 = 64^2$$$.

Ярик уже выбрал $$$n$$$ нот, которые он хочет использовать в своей новой мелодии. Однако, так как их номера могут быть очень большими, он записал их в виде массива $$$a$$$ длины $$$n$$$, тогда нота $$$i$$$ равна $$$b_i = 2^{a_i}$$$. Числа в массиве $$$a$$$ могут повторяться.

Мелодия будет состоять из нескольких сочетаний двух нот. Ярику стало интересно, сколько существует пар нот $$$b_i, b_j$$$ $$$(i < j)$$$ таких, что сочетание $$$(b_i, b_j)$$$ равно сочетанию $$$(b_j, b_i)$$$. Иначе говоря, он хочет посчитать количество пар $$$(i, j)$$$ $$$(i < j)$$$ таких, что $$$b_i^{b_j} = b_j^{b_i}$$$. Помогите ему найти количество таких пар.

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

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

В первой строке каждого набора входных данных дано одно целое число $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$) — длина массива.

В следующей строке даны $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$) — массив $$$a$$$.

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

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

Для каждого набора входных данных выведите искомое количество пар, удовлетворяющих данному условию.

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