Сумма НОД

Ограничение по времени выполнения 1 секунда

Ограничение по использованию памяти 128 мегабайт

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

1 \leq i < j \leq n \sum НОД (a_{i}, a_{j})

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

В первой строке задано количество тестов $t (1 < t < 100)$ . Каждый тест состоит из одной строки и содержит количество входных чисел $n (1 < n < 100)$ , за которым следуют $n$ натуральных чисел. Все входные числа не превышают $1 0^{6}$ .

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

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

Примеры

Ввод #1

Ответ #1

Примечание

Для третьего примера ответ равен

НОД (125, 15) + НОД (125, 25) + НОД (15, 25) = 5 + 25 + 5 = 35

Отправки 2K

Коэффициент принятия 62 %