One important contest will take place on the most famous programming platform (Topforces) very soon!

The authors have a pool of $n$ problems and should choose at most three of them into this contest. The prettiness of the $i$-th problem is $a_i$. The authors have to compose the most pretty contest (in other words, the cumulative prettinesses of chosen problems should be maximum possible).

But there is one important thing in the contest preparation: because of some superstitions of authors, the prettinesses of problems cannot divide each other. In other words, if the prettinesses of chosen problems are $x, y, z$, then $x$ should be divisible by neither $y$, nor $z$, $y$ should be divisible by neither $x$, nor $z$ and $z$ should be divisible by neither $x$, nor $y$. If the prettinesses of chosen problems are $x$ and $y$ then neither $x$ should be divisible by $y$ nor $y$ should be divisible by $x$. Any contest composed from one problem is considered good.

Your task is to find out the maximum possible total prettiness of the contest composed of at most three problems from the given pool.

You have to answer $q$ independent queries.

If you are Python programmer, consider using PyPy instead of Python when you submit your code.


-----Input-----

The first line of the input contains one integer $q$ ($1 \le q \le 2 \cdot 10^5$) — the number of queries.

The first line of the query contains one integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the number of problems.

The second line of the query contains $n$ integers $a_1, a_2, \dots, a_n$ ($2 \le a_i \le 2 \cdot 10^5$), where $a_i$ is the prettiness of the $i$-th problem.

It is guaranteed that the sum of $n$ over all queries does not exceed $2 \cdot 10^5$.


-----Output-----

For each query print one integer — the maximum possible cumulative prettiness of the contest composed of at most three problems from the given pool of problems in the query.


-----Example-----
Input
3
4
5 6 15 30
4
10 6 30 15
3
3 4 6

Output
30
31
10
[{"code": "import sys\ninput = sys.stdin.readline\n\nq=int(input())\nfor testcase in range(q):\n    n=int(input())\n    A=sorted(set(map(int,input().split())),reverse=True)\n    L=len(A)\n\n    #print(A)\n    ANS=A[0]\n    for i in range(L):\n        NOW0=A[i]\n        NOW1=0\n\n        flag=0\n        for j in range(i+1,L):\n            if NOW0%A[j]!=0:\n                NOW1=A[j]\n                ANS=max(ANS,NOW0+NOW1)\n\n                for k in range(j+1,L):\n                    if NOW0%A[k]!=0 and NOW1%A[k]!=0:\n                        ANS=max(ANS,NOW0+NOW1+A[k])\n                        #print(\"!\",ANS)\n                        break\n\n                break\n\n    print(ANS)\n        \n\n", "passed": true, "time": 0.15, "memory": 14236.0, "status": "done"}, {"code": "def calc(X, Y):\n    if len(Y) == 3: return sum(Y)\n    for x in X:\n        for y in Y:\n            if y % x == 0: break\n        else:\n            return calc([i for i in X if i != x], sorted(Y+[x])[::-1])\n    return sum(Y)\nfor _ in range(int(input())):\n    N = int(input())\n    A = sorted(set([int(a) for a in input().split()]))[::-1]\n    print(max(calc(A, []), calc(A[1:], [])))\n", "passed": true, "time": 0.96, "memory": 14312.0, "status": "done"}, {"code": "def calc(X, Y):\n    if len(Y) == 3: return sum(Y)\n    for x in X:\n        for y in Y:\n            if y % x == 0: break\n        else:\n            return calc([i for i in X if i != x], sorted(Y+[x])[::-1])\n    return sum(Y)\nfor _ in range(int(input())):\n    N = int(input())\n    A = sorted(set([int(a) for a in input().split()]))[::-1]\n    print(max(calc(A, []), calc(A[1:], [])))\n", "passed": true, "time": 0.21, "memory": 14428.0, "status": "done"}, {"code": "t=int(input())\nfor _ in range(t):\n    n=int(input())\n    ns=list(map(int,input().split()))\n    ns.sort(reverse=True)\n    from collections import OrderedDict\n    ns=list(OrderedDict.fromkeys(ns))\n\n    m=ns[0]\n    ans=m\n    if m%30==0 and (m//2) in ns and (m//3) in ns and (m//5) in ns:\n        ans=(m//30)*31\n    c=m\n    for i in range(len(ns)):\n        if m%ns[i]!=0:\n            c+=ns[i]\n            for j in range(i+1,len(ns)):\n                if m%ns[j]!=0 and ns[i]%ns[j]!=0:\n                    c+=ns[j]\n                    break\n            break\n    ans=max(ans,c)\n    print(ans)", "passed": true, "time": 0.14, "memory": 14156.0, "status": "done"}, {"code": "def calcSum(first):\n    nonlocal m\n    s = m[first]\n    k = 1\n    for i in range(first + 1, len(m)):\n        yes = True\n        for j in range(first, i):\n            if m[j] % m[i] == 0:\n                yes = False\n                break\n        if yes:\n            s += m[i]\n            k += 1\n            if k == 3: break\n    return s\n    \n\nimport sys\nnnn = int(input())\nfor _ in range(nnn):\n    n = int(sys.stdin.readline())\n    a = list(map(int, sys.stdin.readline().split()))\n    if n == 1:\n        print(a[0])\n        continue\n    if n == 2:\n        if a[0]%a[1] == 0 or a[1]%a[0] == 0:\n            print(max(a))\n        else:\n            print(sum(a))\n        continue\n    a.sort(reverse = True)\n    m = [a[0]]\n    for i in range(1, len(a)):\n        if a[i] == a[i-1]: continue\n        yes = True\n        for j in range(1, len(m)):\n            if m[j] % a[i] == 0:\n                yes = False\n                break\n        if yes:\n            m.append(a[i])\n            if len(m) >= 10:\n                break\n\n##    print(m)\n            \n    s1 = calcSum(0)\n    if len(m) > 1:\n        s2 = calcSum(1)\n    else:\n        s2 = 0\n\n    s = max(s1, s2)\n\n    print (s)\n##    if nnn == 16383:\n##        if _>890:\n##            print(m, ' - ', a, '-', s)\n##    else:\n##        print(s)\n\n        \n        \n", "passed": true, "time": 0.15, "memory": 14360.0, "status": "done"}, {"code": "def find(A):\n    if len(A)==0:\n        return 0\n    #A=sorted(A,reverse=True)\n    checked=[0]*len(A)\n    temp=[]\n    for i in range(len(A)):\n        if len(temp)<3 and checked[i]==0:\n            temp+=[A[i]]\n            for j in range(i+1,len(A)):\n                if A[i]%A[j]==0:\n                    checked[j]=1\n        if len(temp)==3:\n            break\n    \n    return sum(temp)\nfrom collections import defaultdict\nfor _ in range(int(input())):\n    input()\n    dic=defaultdict(int)\n    A=list(map(int,input().strip().split(' ')))\n    for i in range(len(A)):\n        dic[A[i]]=0\n    A=sorted([x for x in dic],reverse=True)\n    print(max(find(A),find(A[1:]),find(A[2:]),find(A[3:])))", "passed": true, "time": 0.14, "memory": 14356.0, "status": "done"}, {"code": "q = int(input())\nfor w in range(q):\n\tn = int(input())\n\tarr = list(map(int,input().split()))\n\tarr = list(set(arr))\n\tarr.sort(reverse=True)\n\tn = len(arr)\n\tans=0\n\tfor i in range(n):\n\t\tans = max(ans,arr[i])\n\t\tfor j in range(i+1,n):\n\t\t\tif arr[i]%arr[j]!=0:\n\t\t\t\tans = max(ans,arr[i]+arr[j])\n\t\t\t\tif j+1<n and ans>= arr[i]+arr[j+1]+arr[j]:\n\t\t\t\t\tbreak\n\t\t\t\tfor k in range(j+1,n):\n\t\t\t\t\tif ans>=arr[i]+arr[j]+arr[k]:\n\t\t\t\t\t\t\tbreak\n\t\t\t\t\tif arr[j]%arr[k]!=0 and arr[i]%arr[k]!=0:\n\t\t\t\t\t\tans = max(ans,arr[i]+arr[j]+arr[k])\n\tprint(ans)\n\n", "passed": true, "time": 0.14, "memory": 14272.0, "status": "done"}, {"code": "q = int(input())\nfor w in range(q):\n\tn = int(input())\n\tarr = list(map(int,input().split()))\n\tarr = list(set(arr))\n\tarr.sort(reverse=True)\n\tn = len(arr)\n\tansarr = [-1 for i in range(n)]\n\tmaxans = 0\n\tfor i in range(n):\n\t\tcurrans = arr[i]\n\t\tfor j in range(i+1,min(i+171,n)):\n\t\t\tif arr[i]%arr[j]!=0:\n\t\t\t\tcurrans = max(currans,arr[i]+arr[j])\n\t\t\t\tif j+1<n and arr[i]+arr[j]+arr[j+1]<=maxans:\n\t\t\t\t\tbreak\n\t\t\t\tfor k in range(j+1,min(j+171,n)):\n\t\t\t\t\tif arr[j]%arr[k]!=0 and arr[i]%arr[k]!=0:\n\t\t\t\t\t\tcurrans = max(currans,arr[i]+arr[j]+arr[k])\n\t\t\t\t\t\tif currans<=maxans:\n\t\t\t\t\t\t\tbreak\n\t\tansarr[i]=currans\n\t\tmaxans = max(maxans,currans)\n\tprint(max(ansarr))", "passed": true, "time": 0.14, "memory": 14108.0, "status": "done"}, {"code": "q = int(input())\nfor i in range(q):\n\tn = int(input())\n\ta = [int(i) for i in input().split()]\n\ta.sort(reverse = True)\n\tfirst = a[0]\n\tsecond = -1\n\tthird = -1\n\tmaxa = a[0]\n\tarr = []\n\tfor i in range(n):\n\t\tif(first%a[i] != 0):\n\t\t\tif(second == -1):\n\t\t\t\tsecond  = a[i]\n\t\t\telif(second%a[i] != 0):\n\t\t\t\tif(third == -1):\n\t\t\t\t\tthird = a[i]\n\t\t\t\telse:\n\t\t\t\t\tbreak\n\tif(maxa%30 == 0):\n\t\tif((maxa//2) in a and ((maxa//3) in a ) and (maxa//5) in a ):\n\t\t\tprint(max(first + max(second,0) + max(third,0),(maxa//2) + (maxa//3) + maxa//5))\n\t\telse:\n\t\t\tprint(max(first,0)+max(second,0)+max(third,0))\n\telse:\n\t\tprint(max(first,0)+max(second,0)+max(third,0))", "passed": true, "time": 0.14, "memory": 14408.0, "status": "done"}, {"code": "q = int(input())\nfor query in range(q):\n\tn = int(input())\n\tl = list(map(int,input().split()))\n\tl.sort()\n\tl.reverse()\n\twy = -1000000000000\n\ta = [l[0]]\n\tu = 1\n\twhile u < n:\n\t\tif l[u] != l[u-1]:\n\t\t\ta.append(l[u])\n\t\tif len(a) > 4:\n\t\t\tbreak\n\t\tu += 1\n\tif (len(a) > 3 and a[1] == a[0] / 2 and a[2] == a[0] / 3 and a[3] == a[0] / 5) or (len(a) > 4 and a[1] == a[0] / 2 and a[2] == a[0] / 3 and a[3] == a[0] /4 and a[4] == a[0] / 5):\n\t\twy = (a[1] + a[2] + a[3])\n\tnowa = [l[i] for i in range(n) if l[0] % l[i] != 0]\n\tnowa.sort()\n\tnowa.reverse()\n\tif len(nowa) > 0:\n\t\tpart = 0\n\t\tfor i in range(1, len(nowa)):\n\t\t\tif nowa[0] % nowa[i] !=0:\n\t\t\t\tpart = nowa[i]\n\t\t\t\tbreak\n\t\twyn = l[0] + nowa[0] + part\n\telse:\n\t\twyn = l[0]\n\tprint(max(wyn, wy))", "passed": true, "time": 0.14, "memory": 14424.0, "status": "done"}, {"code": "import sys\ninput = sys.stdin.readline\n\nq=int(input())\nfor testcase in range(q):\n    n=int(input())\n    A=sorted(set(map(int,input().split())),reverse=True)\n    L=len(A)\n\n    #print(A)\n    ANS=A[0]\n    for i in range(L):\n        NOW0=A[i]\n        NOW1=0\n\n        flag=0\n        for j in range(i+1,L):\n            if NOW0%A[j]!=0:\n                NOW1=A[j]\n                ANS=max(ANS,NOW0+NOW1)\n\n                for k in range(j+1,L):\n                    if NOW0%A[k]!=0 and NOW1%A[k]!=0:\n                        ANS=max(ANS,NOW0+NOW1+A[k])\n                        #print(\"!\",ANS)\n                        break\n\n                break\n\n    print(ANS)\n", "passed": true, "time": 0.14, "memory": 14280.0, "status": "done"}, {"code": "for i in range(int(input())):\n    n = int(input())\n    w = set()\n    [w.add(int(j)) for  j in input().split()]\n    data = list(w)\n    data.sort()\n    nums = [data[-1]]\n    ind = len(data) - 2\n    cnt = 1\n    while ind >= 0:\n        #print(ind, nums)\n        if cnt == 1:\n            if nums[0] % data[ind] != 0:\n                nums.append(data[ind])\n                cnt += 1\n        else:\n            if nums[0] % data[ind] != 0 and nums[1] % data[ind] != 0 :\n                nums.append(data[ind])\n                break\n        ind -= 1\n    ans = sum(nums)\n    if len(data) >= 2:\n \n        nums2 = [data[-2]]\n        ind = len(data) - 3\n \n        cnt = 1\n        while ind >= 0:\n            if cnt == 1:\n                if nums2[0] % data[ind] != 0:\n                    nums2.append(data[ind])\n                    cnt += 1\n            else:\n                if nums2[0] % data[ind] != 0 and nums2[1] % data[ind] != 0 :\n                    nums2.append(data[ind])\n                    break\n            ind -= 1\n        ans = max(ans, sum(nums2))\n    print(ans)", "passed": true, "time": 0.21, "memory": 14316.0, "status": "done"}, {"code": "import sys\ninput = sys.stdin.readline\n \nt = int(input().strip())\nfor _ in range(t):\n    n = int(input().strip())\n    ls = list(map(int, input().strip().split()))\n    ls = list(set(ls))\n    ls.sort()\n    n = len(ls)\n    if n==1:\n        print(ls[0])\n    elif n==2:\n        if ls[1]%ls[0]==0: print(ls[1])\n        else: print(ls[0]+ls[1])\n    else:\n        ans = []\n        for i in range(n-1, n-1-3, -1):\n            c = i\n            for j in range(c-1, -1, -1):\n                if ls[c]%ls[j]!=0: b = j; break\n            else: ans.append(ls[c]); continue\n            for k in range(b-1, -1, -1):\n                if ls[c]%ls[k]!=0 and ls[b]%ls[k]!=0: a = k; break\n            else: ans.append(ls[c]+ls[b]); continue\n            ans.append(ls[c]+ls[b]+ls[a])\n        print(max(ans))\n", "passed": true, "time": 0.14, "memory": 14148.0, "status": "done"}, {"code": "q = int(input())\nans = []\nfor w in range(q):\n    n = int(input())\n    a = [int(x) for x in input().split()]\n    a.sort()\n    a = a[::-1]\n    a1 = 0\n    b1 = 0\n    c1 = 0\n    a1 = a[0]\n    for i in range(n):\n        if a1 % a[i] != 0:\n            b1 = a[i]\n            break\n    for i in range(n):\n        if a1 % a[i] != 0 and b1 % a[i] != 0:\n            c1 = a[i]\n            break\n    a2 = 0\n    b2 = 0\n    c2 = 0\n    if a1 % 2 == 0:\n        for i in range(n):\n            if a[i] == a1 // 2:\n                a2 = a[i]\n                break\n    if a1 % 3 == 0:\n        for i in range(n):\n            if a[i] == a1 // 3:\n                b2 = a[i]\n                break\n    if a1 % 5 == 0:\n        for i in range(n):\n            if a[i] == a1 // 5:\n                c2 = a[i]\n                break\n    ans.append(max(a1 + b1 + c1, a2 + b2 + c2))\nfor i in range(q):\n    print(ans[i])\n\n", "passed": true, "time": 0.15, "memory": 14364.0, "status": "done"}, {"code": "def cal(sorted_list, size):\n    max_sum = 0\n    for k in range(len(sorted_list)):\n        max_sum = max(sorted_list[k], max_sum)\n        for i in range(k+1,size):\n            temp_1 = sorted_list[i]\n            if sorted_list[k]%temp_1 != 0:\n                if i+1 < size and max_sum >= sorted_list[k] + sorted_list[i] + sorted_list[i+1]:\n                    break\n                check_sum = sorted_list[k] + temp_1\n                max_sum = max(max_sum, check_sum)\n                for j in range(i+1, size):\n                    if max_sum >= sorted_list[k] + sorted_list[i] + sorted_list[j]:\n                        break\n                    temp_2 = sorted_list[j]\n                    if sorted_list[k] % temp_2 != 0 and temp_1 % temp_2 != 0:\n                        max_sum =  max(max_sum, check_sum + temp_2)\n                        break\n    return max_sum\n\ndef solve():\n    no_querries = int(input())\n    output = []\n    for i in range(no_querries):\n        size = int(input())\n        alist_raw = input().split()\n        alist = [int(x) for x in alist_raw]\n        alist.sort(reverse=True)\n        alist = unique(alist)\n        output.append(cal(alist, len(alist)))\n    for x in output:\n        print(x)\n\ndef unique(alist):\n    unique = [alist[0]]\n    for i in range(1,len(alist)):\n        if alist[i] < unique[len(unique)-1]:\n            unique.append(alist[i])\n    return unique\n\nsolve()", "passed": true, "time": 0.15, "memory": 14184.0, "status": "done"}, {"code": "answer = []\nfor _ in range(int(input())):\n    input()\n    l = sorted(map(int, input().split()))\n    other = 0\n    if l[-1] % 30 == 0 and len(set(l) & {l[-1] // 2, l[-1] // 3, l[-1] // 5}) == 3:\n        other = (31 * l[-1]) // 30\n    while len(l) >= 2 and l[-1] % l[-2] == 0:\n        del l[-2]\n    while len(l) >= 3 and 0 in (l[-1] % l[-3], l[-2] % l[-3]):\n        del l[-3]\n    answer.append(str(max(other, sum(l[-3:]))))\nprint(\"\\n\".join(answer))", "passed": true, "time": 0.14, "memory": 14340.0, "status": "done"}, {"code": "3.6\n\n'''\n        .__     .__                                _______   _______ _________\n  ______|  |__  |__|  ____    ____ _______ _____   \\   _  \\  \\   _  \\\\______  \\\n /  ___/|  |  \\ |  | /    \\  /  _ \\\\_  __ \\\\__  \\  /  /_\\  \\ /  /_\\  \\   /    /\n \\___ \\ |   Y  \\|  ||   |  \\(  <_> )|  | \\/ / __ \\_\\  \\_/   \\\\  \\_/   \\ /    /\n/____  >|___|  /|__||___|  / \\____/ |__|   (____  / \\_____  / \\_____  //____/\n     \\/      \\/          \\/                     \\/        \\/        \\/\n\n'''\n# Run locally with python3.6 -O code.py to run in not debug mode. [ONLINE_JUDGE]\n# rm ~/pipe2; mkfifo ~/pipe2 ; ./code.py < ~/pipe2 | ./interactive.py > ~/pipe2\n# rm ~/pipe2; mkfifo ~/pipe2 ; ./code.py < ~/pipe2 | ./matcher.py > ~/pipe2\n\n# one-way\n# ./haha.py > input.txt ; ./code.py < input.txt\n\nimport sys\n\ndef eprint(*args, **kwargs):\n    if __debug__:\n        print(*args, file=sys.stderr, **kwargs)\n\ndef __starting_point():\n    q = int(input())\n    while q > 0:\n        ans = 0\n        q -= 1\n        x = y = z = 0\n        # eprint(f's: {s}, q:{q}')\n        n = int(input())\n        arr = list(set(map(int, input().split(' '))))\n        arr.sort()\n        # print(arr)\n        if arr == [2, 3, 5]:\n            print(10)\n            continue\n\n        z = arr[len(arr)-1]\n        if (z%2==0) and (z%3==0) and (z%5==0) and (arr.count(z//2) > 0) and (arr.count(z//3) > 0) and (arr.count(z//5) > 0):\n            ans = max(ans, (z//2) + (z//3) + (z//5))\n        \n        res = []\n        while len(arr) > 0 and len(res) < 3:\n            c = arr.pop()\n            flag = 1\n            for x in res:\n                flag &= ((x%c) != 0)\n            if flag == 1:\n                res.append(c)\n\n        \n        ans = max(ans, sum(res))\n        print(ans)\n        # eprint(f'x:{x}, y:{y}, z:{z}')\n\n__starting_point()", "passed": true, "time": 0.14, "memory": 14188.0, "status": "done"}, {"code": "import sys\nq = int(input())\nlines = sys.stdin.readlines()\nres = []\ndef getMax(numset):\n    n = max(numset)\n    numset = set([j for j in numset if n % j != 0])\n    return (n , numset)\n\nfor i in range(q):\n    n = int(lines[2 * i])\n    m = []\n    numset = set()\n    for j in lines[2 * i + 1].split():\n        numset.add(int(j))\n    total = max(numset)\n    n = total\n    if n // 2 in numset and n // 3 in numset and n // 5 in numset:\n        total = n // 2 + n // 3 + n // 5\n    for _ in range(3):\n        if len(numset) == 0:\n            break\n        n, numset = getMax(numset)\n        m.append(n)\n        if sum(m) > total:\n            total = sum(m)\n    res.append(str(total))\nprint('\\n'.join(res))\n\n", "passed": true, "time": 0.14, "memory": 14208.0, "status": "done"}, {"code": "M = lambda:list(map(int, input().split()))\nq = int(input())\nfor qer in range(q):\n    n = int(input())    \n    a = M()\n    \n    D = {}\n    \n    for i in a:\n        D[i] = 1\n        \n    a.sort(reverse = True)\n    \n    def get_max():\n        for i in a:\n            if D[i]:\n                return i\n        return 0\n    \n    def fix(x):\n        for i in a:\n            if x % i == 0:\n                D[i] = 0\n    \n    L = [0] * 3\n    for i in range(3):\n        L[i] = get_max()\n        if L[i] == 0:\n            break\n        fix(L[i])\n    \n    ans = sum(L)\n    if a[0] % 2 == 0 and a[0] % 3 == 0 and a[0] % 5 == 0:\n        if a[0] / 2 in D and a[0] / 3 in D and a[0] / 5 in D:\n            ans = max(ans, a[0] // 2 + a[0] // 3 + a[0] // 5)\n    \n    print(ans)", "passed": true, "time": 0.14, "memory": 14172.0, "status": "done"}, {"code": "# https://codeforces.com/contest/1183/problem/F\n\n\ndef solve(a_s):\n    a_s = set(a_s)\n    n = max(a_s)\n    largest = n\n    if n // 2 in a_s and n // 3 in a_s and n // 5 in a_s:\n        largest = n // 2 + n // 3 + n // 5\n    m = []\n    for _ in range(3):\n        if not a_s:\n            break\n        n = max(a_s)\n        a_s = set([j for j in a_s if n % j != 0])\n        m.append(n)\n        if sum(m) > largest:\n            largest = sum(m)\n    return largest\n\n\nq = int(input())\n\nfor _ in range(q):\n    n = int(input())\n    a_s = list(map(int, input().split()))\n    print(solve(a_s))", "passed": true, "time": 0.15, "memory": 14304.0, "status": "done"}]