D. НОД меньших
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Пусть $$$a$$$, $$$b$$$ и $$$c$$$ — целые числа. Определим функцию $$$f(a, b, c)$$$ следующим образом.

Упорядочить числа $$$a$$$, $$$b$$$, $$$c$$$ таким образом, чтобы выполнялось $$$a \le b \le c$$$. Затем вернуть $$$\gcd(a, b)$$$, где $$$\gcd(a, b)$$$ обозначает наибольший общий делитель (НОД) чисел $$$a$$$ и $$$b$$$.

Иными словами, мы берем $$$\gcd$$$ из $$$2$$$ меньших значений и игнорируем наибольшее.

Вам дан массив $$$a$$$ длины $$$n$$$. Вычислите сумму $$$f(a_i, a_j, a_k)$$$ для всех $$$i$$$, $$$j$$$, $$$k$$$ таких, что $$$1 \le i < j < k \le n$$$.

Более формально, вычислите $$$$$$\sum_{i = 1}^n \sum_{j = i+1}^n \sum_{k =j +1}^n f(a_i, a_j, a_k).$$$$$$

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

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

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$3 \le n \le 8 \cdot 10^4$$$) — длину массива $$$a$$$.

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

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

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

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

Пример
Входные данные
2
5
2 3 6 12 17
8
6 12 8 10 15 12 18 16
Выходные данные
24
203
Примечание

В первом наборе входных данных значения $$$f$$$ следующие:

  • $$$i=1$$$, $$$j=2$$$, $$$k=3$$$, $$$f(a_i,a_j,a_k)=f(2,3,6)=\gcd(2,3)=1$$$;
  • $$$i=1$$$, $$$j=2$$$, $$$k=4$$$, $$$f(a_i,a_j,a_k)=f(2,3,12)=\gcd(2,3)=1$$$;
  • $$$i=1$$$, $$$j=2$$$, $$$k=5$$$, $$$f(a_i,a_j,a_k)=f(2,3,17)=\gcd(2,3)=1$$$;
  • $$$i=1$$$, $$$j=3$$$, $$$k=4$$$, $$$f(a_i,a_j,a_k)=f(2,6,12)=\gcd(2,6)=2$$$;
  • $$$i=1$$$, $$$j=3$$$, $$$k=5$$$, $$$f(a_i,a_j,a_k)=f(2,6,17)=\gcd(2,6)=2$$$;
  • $$$i=1$$$, $$$j=4$$$, $$$k=5$$$, $$$f(a_i,a_j,a_k)=f(2,12,17)=\gcd(2,12)=2$$$
  • $$$i=2$$$, $$$j=3$$$, $$$k=4$$$, $$$f(a_i,a_j,a_k)=f(3,6,12)=\gcd(3,6)=3$$$;
  • $$$i=2$$$, $$$j=3$$$, $$$k=5$$$, $$$f(a_i,a_j,a_k)=f(3,6,17)=\gcd(3,6)=3$$$;
  • $$$i=2$$$, $$$j=4$$$, $$$k=5$$$, $$$f(a_i,a_j,a_k)=f(3,12,17)=\gcd(3,12)=3$$$;
  • $$$i=3$$$, $$$j=4$$$, $$$k=5$$$, $$$f(a_i,a_j,a_k)=f(6,12,17)=\gcd(6,12)=6$$$.
Сумма по всем тройкам равна $$$1+1+1+2+2+2+3+3+3+6=24$$$.

Во втором наборе входных данных существует $$$56$$$ способов выбора значений $$$i$$$, $$$j$$$, $$$k$$$. Сумма по всем $$$f(a_i,a_j,a_k)$$$ равна $$$203$$$.