Очередным вечером понедельника Даня сидел в библиотеке и решал задачи по программированию. Он очень любил проводить время за решением задач, но больше он любил гордиться уже решенными задачами перед другими ребятами. Его знакомый знал, что Даня мастер в своем деле и попросил его помочь с одним незамысловатым упражнением.
Даня впал в ступор от таких упражнений, но терять репутацию опытного программиста ему не хочется. Поэтому он обратился к вам за помощью. А задача была такая:
Рассмотрим функцию минимального нетривиального делителя $$$M(x) = d$$$, где $$$d$$$ — минимальное число больше единицы, на которое делится $$$x$$$. У единицы нет таких делителей, поэтому полагается $$$M(1) = 0$$$.
Например, $$$M(12) = 2$$$, $$$M(35) = 5$$$, $$$M(179) = 179$$$.
По заданному массиву $$$a_1, \ldots, a_n$$$ длины $$$n$$$ требуется для каждого $$$k$$$ от $$$1$$$ до $$$n$$$ вычислить значение следующего выражения:
$$$$$$ \sum_{i=1}^{k-1} \sum_{j=i+1}^{k} M\left( \frac{a_i a_j}{\gcd(a_i, a_j)^2} \right) $$$$$$
Здесь $$$\gcd(x, y)$$$ обозначает наибольший общий делитель (НОД) чисел $$$x$$$ и $$$y$$$.
Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1 \le n \le 150\,000$$$) — размер массива.
Следующая строка каждого набора входных данных содержит $$$n$$$ чисел $$$a_i$$$ ($$$2 \le a_i \le 1\,000\,000$$$) — сам массив $$$a$$$.
Гарантиурется, что сумма $$$n$$$ по всем наборам не превосходит $$$150\,000$$$.
Для каждого набора входных данных выведите $$$n$$$ чисел — значение искомый суммы для каждого $$$1 \le k \le n$$$.
432 4 852 3 4 5 61010 12 15 20 10 13 17 11 25 305999979 999749 999959 999917 999671
0 2 60 2 6 13 220 2 6 13 19 30 54 87 113 1330 999749 2999457 5999040 9997724
