Сумма НСД

Обмеження на час виконання 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%