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