Задачи
Сумма НОД
Сумма НОД
Для заданных $n$ натуральных чисел $a_1, a_2, ..., a_n$ найдите сумму НОД (наибольших общих делителей) всех возможных пар этих чисел.
$$
\sum_{\mathclap{1 \le i < j\le n}} НОД(a_i,a_j)
$$
\InputFile
В первой строке задано количество тестов $t\:(1 < t < 100)$. Каждый тест состоит из одной строки и содержит количество входных чисел $n\:(1 < n < 100)$, за которым следуют $n$ натуральных чисел. Все входные числа не превышают $10^6$.
\OutputFile
Для каждого теста в отдельной строке вывести сумму \textbf{НОД} всех возможных пар.
\Note
Для третьего примера ответ равен
$$
НОД(125,15) + НОД(125,25) + НОД(15,25) = 5 + 25 + 5 = 35
$$
Входные данные #1
3 4 10 20 30 40 3 7 5 12 3 125 15 25
Выходные данные #1
70 3 35