Сума НСД#6941

Сума НСД

1 секунда
128 мегабайтів
Легка

Для заданих натуральних чисел 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), за яким йдуть натуральних чисел. Усі вхідні числа не перевищують 10^6.

Вихідні дані

Для кожного тесту у окремому рядку виведіть суму НСД усіх можливих пар.

Приклади

Приклад 1

Loading
Loading

Примітка

Для третього прикладу відповідь дорівнює

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