Для заданих натуральних чисел a_1, a_2, ..., a_n знайдіть суму НСД (найбільших спільних дільників) усіх можливих пар цих чисел.
У першому рядку задано кількість тестів t~(1 < t < 100). Кожен тест складається з одного рядка та містить кількість вхідних чисел n~(1 < n < 100), за яким йдуть натуральних чисел. Усі вхідні числа не перевищують 10^6.
Для кожного тесту у окремому рядку виведіть суму НСД усіх можливих пар.
Приклад 1
Для третього прикладу відповідь дорівнює