from itertools import combinations as c; from math import gcd
for i in range(int(input())):print(sum([gcd(k,h) for k,h in c((lambda b:[int(j) for j in b][1:int(b[0])+1])(input().split()),2)]))