Задачі
Сумма НСД
Сумма НСД
Для заданих 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