Пожалуйста, прочтите новое правило об ограничении использования AI-инструментов. ×
Изменения рейтингов за последние раунды временно удалены. Скоро они будут возвращены. ×

E. Префиксные НОД
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Так как Мансур устал делать легенды, легенды на эту задачу не будет.

Дан массив натуральных чисел $$$a_1, a_2, \ldots, a_n$$$. В нём можно переставить элементы произвольным образом. Требуется узнать минимально возможное значение выражения $$$$$$\gcd(a_1) + \gcd(a_1, a_2) + \ldots + \gcd(a_1, a_2, \ldots, a_n),$$$$$$ где $$$\gcd(a_1, a_2, \ldots, a_n)$$$ обозначает наибольший общий делитель (НОД) чисел $$$a_1, a_2, \ldots, a_n$$$.

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

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит единственное число $$$n$$$ ($$$1 \le n \le 10^5$$$) — размер массива.

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^5$$$) — исходный массив.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превышает $$$10^5$$$.

Гарантируется, что сумма $$$\max(a_1, a_2, \ldots, a_n)$$$ по всем наборам входных данных не превышает $$$10^5$$$.

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

Для каждого набора входных данных выведите единственное число в отдельной строке — ответ на задачу.

Пример
Входные данные
5
3
4 2 2
2
6 3
3
10 15 6
5
6 42 12 52 20
4
42 154 231 66
Выходные данные
6
6
9
14
51
Примечание

В первом наборе входных данных можно переставить элементы следующим образом: $$$[2, 4, 2]$$$, тогда ответом будет $$$\gcd(2) + \gcd(2, 4) + \gcd(2, 4, 2) = 2 + 2 + 2 = 6$$$.

В третьем наборе входных данных можно переставить элементы следующим образом: $$$[6, 10, 15]$$$, тогда ответом будет $$$\gcd(6) + \gcd(6, 10) + \gcd(6, 10, 15) = 6 + 2 + 1 = 9$$$.