====== GCD 합 ======

===== 풀이 =====
  * 그냥 모든 쌍에 대해서 GCD를 다 구해보는것으로 충분하다.
  * 시간복잡도는 O(n^2*logm)

===== 코드 =====
<dkpr py>
"""Solution code for "BOJ 9613. GCD 합".

- Problem link: https://www.acmicpc.net/problem/9613
- Solution link: http://www.teferi.net/ps/problems/boj/9613
"""

import itertools
import math


def main():
    t = int(input())
    for _ in range(t):
        # pylint: disable=unused-variable
        n, *nums = [int(x) for x in input().split()]
        print(sum(math.gcd(*t) for t in itertools.combinations(nums, 2)))


if __name__ == '__main__':
    main()
</dkpr>

{{tag>BOJ ps:problems:boj:실버_3}}