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