Сумма НОД - Задачи

Для заданных n натуральных чисел найдите сумму НОД (наибольших общих делителей) всех возможных пар этих чисел.

Входные данные

В первой строке задано количество тестов n (1 < n < 100). Каждый тест состоит из одной строки и содержит количество входных чисел m (1 < m < 100), за которым следуют m натуральных чисел. Все входные числа натуральные, не превышающие 10⁶.

Выходные данные

Для каждого теста в отдельной строке вывести сумму НОД всех возможных пар.

Лимит времени 1 секунда

Лимит использования памяти 128 MiB

Входные данные #1

3
4 10 20 30 40
3 7 5 12
3 125 15 25

Выходные данные #1

70
3
35

Источник 2013 ACM-ICPC Asia Phuket Regional Programming Contest, Practice Session, November 21