eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Сумма НСД

Сумма НСД

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB

Для заданих 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
Джерело 2013 ACM-ICPC Asia Phuket Regional Programming Contest, Practice Session, November 21