G. Скибидус и ложь
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Скибидус был похищен инопланетянами с Амога! Скибидус пытается выкрутиться, но инопланетяне с Амога не верят ему. Чтобы доказать, что он не врет, инопланетяне с Амога попросили его решить эту задачу:

Целое число $$$x$$$ считается полупростым, если его можно записать в виде $$$p \cdot q$$$, где $$$p$$$ и $$$q$$$ — (не обязательно разные) простые числа. Например, $$$9$$$ является полупростым, так как его можно записать как $$$3 \cdot 3$$$, а $$$3$$$ является простым числом.

Скибидусу был дан массив $$$a$$$, содержащий $$$n$$$ целых чисел. Он должен сообщить количество пар $$$(i, j)$$$ таких, что $$$i \leq j$$$ и $$$\operatorname{lcm}(a_i, a_j)$$$$$$^{\text{∗}}$$$ является полупростым.

$$$^{\text{∗}}$$$Для двух целых чисел $$$x$$$ и $$$y$$$, $$$\operatorname{lcm}(x, y)$$$ обозначает наименьшее общее кратное $$$x$$$ и $$$y$$$.

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

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

Первая строка каждого набора входных данных содержит целое число $$$n$$$ ($$$2 \leq n \leq 2 \cdot 10^5$$$).

Следующая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$2 \leq a_i \leq n$$$).

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

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

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

Пример
Входные данные
3
4
2 2 3 4
6
2 2 3 4 5 6
9
2 2 4 5 7 8 9 3 5
Выходные данные
5
12
18
Примечание

В первом наборе входных данных $$$5$$$ пар индексов: $$$(1, 3)$$$, $$$(1, 4)$$$, $$$(2, 3)$$$, $$$(2, 4)$$$ и $$$(4, 4)$$$.