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

Это сложная версия задачи. Единственное различие состоит в том, что в этой версии $$$n \leq 5 \cdot 10^5$$$ и сумма $$$n$$$ по всем наборам входных данных не превосходит $$$5 \cdot 10^5$$$.

Вам дана перестановка $$$p$$$ длины $$$n$$$. Посчитайте количество пар индексов $$$1 \leq i < j \leq n$$$, таких что $$$p_i \cdot p_j$$$ делится без остатка на $$$i \cdot j$$$.

Перестановка — это последовательность из $$$n$$$ целых чисел, в которой каждое целое число от $$$1$$$ до $$$n$$$ встречается ровно по одному разу. Например, $$$[1]$$$, $$$[3,5,2,1,4]$$$, $$$[1,3,2]$$$ — перестановки, а $$$[2,3,2]$$$, $$$[4,3,1]$$$, $$$[0]$$$ — нет.

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

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

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

Вторая строка каждого набора входных данных содержит $$$n$$$ различных целых чисел $$$p_1, p_2, \ldots, p_n$$$ ($$$1 \leq p_i \leq n$$$) — перестановку $$$p$$$.

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

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

Для каждого набора входных данных выведите количество пар индексов $$$1 \leq i < j \leq n$$$, таких что $$$p_i \cdot p_j$$$ делится без остатка на $$$i \cdot j$$$.

Пример
Входные данные
6
1
1
2
1 2
3
2 3 1
5
2 4 1 3 5
12
8 9 7 12 1 10 6 3 2 4 11 5
15
1 2 4 6 8 10 12 14 3 9 15 5 7 11 13
Выходные данные
0
1
1
3
9
3
Примечание

В первом наборе входных данных нет ни одной пары индексов, так как размер перестановки равен $$$1$$$.

Во втором наборе входных данных есть одна пара индексов $$$(1, 2)$$$ и она подходит.

В третьем наборе входных данных подходит пара индексов $$$(1, 2)$$$.

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