Codeforces Round 909 (Div. 3) |
---|
Закончено |
Ярик — большой фанат разной музыки. Но Ярик любит не только слушать музыку, но и писать её. Больше всего он любит электронную музыку, поэтому он придумал свою собственную систему нот, которая, по его мнению, лучше всего подходит для неё.
Так как Ярик ещё и увлекается информатикой, то в его системе ноты обозначаются числами вида $$$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$$$.
Для каждого набора входных данных выведите искомое количество пар, удовлетворяющих данному условию.
51243 1 3 221000 100031 1 1192 4 1 6 2 8 5 4 2 10 5 10 8 7 4 3 2 6 10
0 2 1 3 19
Название |
---|