G2. Магические тройки (сложная версия)
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это сложная версия задачи. Единственное отличие в том, что в этой версии $$$a_i \le 10^9$$$.

Для данной последовательности целых чисел $$$a$$$ длины $$$n$$$, тройка $$$(i, j, k)$$$ называется магической, если

  • $$$1 \le i, j, k \le n$$$.
  • $$$i$$$, $$$j$$$, $$$k$$$ — попарно различны.
  • существует некоторое целое положительное число $$$b$$$, такое что $$$a_i \cdot b = a_j$$$, а $$$a_j \cdot b = a_k$$$.

Коля получил в подарок последовательность целых чисел $$$a$$$, и теперь хочет посчитать количество магических троек для нее. Помогите ему в этом!

Обратите внимание, что нет ограничений на порядок чисел $$$i$$$, $$$j$$$ и $$$k$$$.

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

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится единственное целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

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

Вторая строка содержит $$$n$$$ чисел $$$a_1, a_2, a_3, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — элементы последовательности $$$a$$$.

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

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

Для каждого набора входных данных выведите одно целое число — количество магических троек для последовательности $$$a$$$.

Пример
Входные данные
7
5
1 7 7 2 7
3
6 2 18
9
1 2 3 4 5 6 7 8 9
4
1000 993 986 179
7
1 10 100 1000 10000 100000 1000000
8
1 1 2 2 4 4 8 8
9
1 1 1 2 2 2 4 4 4
Выходные данные
6
1
3
0
9
16
45
Примечание

В первом примере существует $$$6$$$ магических троек для последовательности $$$a$$$ — $$$(2, 3, 5)$$$, $$$(2, 5, 3)$$$, $$$(3, 2, 5)$$$, $$$(3, 5, 2)$$$, $$$(5, 2, 3)$$$, $$$(5, 3, 2)$$$.

Во втором примере существует единственная магическая тройка для последовательности $$$a$$$ — $$$(2, 1, 3)$$$.