Chef has a sequence of positive integers $A_1, A_2, \ldots, A_N$. He wants to split this sequence into two non-empty (not necessarily contiguous) subsequences $B$ and $C$ such that $\mathrm{GCD}\,(B) + \mathrm{GCD}\,(C)$ is maximum possible. Help him find this maximum value.
Note: The greatest common divisor (GCD) of a sequence of positive integers is the largest positive integer that divides each element of this sequence. For example, the GCD of the sequence $(8, 12)$ is $4$.

-----Input-----
- The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
- The first line of each test case contains a single integer $N$.
- The second line contains $N$ space-separated integers $A_1, A_2, \ldots, A_N$.

-----Output-----
For each test case, print a single line containing one integer — the maximum value of $\mathrm{GCD}\,(B) + \mathrm{GCD}\,(C)$.

-----Constraints-----
- $1 \le T \le 10$
- $2 \le N \le 10^5$
- $1 \le A_i \le 10^9$ for each valid $i$

-----Subtasks-----
Subtask #1 (20 points): $2 \le N \le 20$
Subtask #2 (80 points): original constraints

-----Example Input-----
1              
4                    
4 4 7 6                    

-----Example Output-----
9

-----Explanation-----
Example case 1: For example, the sequence $A$ can be divided into subsequences $B = (4, 4, 6)$ and $C = (7)$.

Difficulty: interview

Starter code:

Solutions:
from math import gcd

__author__ = 'Prateek'


def test():
    n = int(input())
    a = list(map(int, input().split()))
    a = list(set(a))
    n = len(a)
    if len(a) == 1:
        print(2 * a[0])
        return
    g1 = [0 for i in range(n)]
    g2 = [0 for i in range(n)]
    g1[0] = a[0]
    g2[n - 1] = a[n - 1]
    for i in range(1, n):
        g1[i] = gcd(g1[i - 1], a[i])
    for i in range(n - 2, -1, -1):
        g2[i] = gcd(g2[i + 1], a[i])
    ans = 0
    for i in range(n):
        if i == 0:
            ans = max(ans, g2[i + 1] + a[i])
        elif i == n - 1:
            ans = max(ans, g1[i - 1] + a[i])
        else:
            ans = max(ans, gcd(g1[i - 1], g2[i + 1]) + a[i])
    print(ans)


if __author__ == 'Prateek':
    t = int(input())
    for _ in range(t):
        test()


from math import gcd
from functools import reduce
for _ in range(int(input())):
    ans = 0
    n = int(input())
    a = list(map(int,input().split()))
    a = list(set(a))
    if len(a) == 1:
        print(a[0]*2)
        continue
    for i in range(len(a)):
        k = a[i]
        del(a[i])
        ans = max(ans, k + reduce(gcd,a))
        a.insert(i,k)
    print(ans)

# cook your dish here
import math 
for _ in range(int(input())):
    n=int(input())
    a=list(map(int,input().split()))
    newa=list(set(a))
    if len(newa)==1:
        print(newa[0]*2)
    elif len(newa)==2:
        print(sum(newa))
    else:
        newa.sort()
        m1=newa.pop()
        m2=newa.pop()
        gcd=newa[0]
        for i in range(1,len(newa)):
            gcd=math.gcd(gcd,newa[i])
            if gcd==1:
                break
        s1=math.gcd(gcd,m1)
        s2=math.gcd(gcd,m2)
        print(max(s1+m2,s2+m1))

# cook your dish here
import math 
for _ in range(int(input())):
    n=int(input())
    a=list(map(int,input().split()))
    newa=list(set(a))
    if len(newa)==1:
        print(newa[0]*2)
    elif len(newa)==2:
        print(sum(newa))
    else:
        newa.sort()
        m1=newa.pop()
        m2=newa.pop()
        gcd=newa[0]
        for i in range(1,len(newa)):
            gcd=math.gcd(gcd,newa[i])
            if gcd==1:
                break
        s1=math.gcd(gcd,m1)
        s2=math.gcd(gcd,m2)
        print(max(s1+m2,s2+m1))

# cook your dish here
import math 
for _ in range(int(input())):
    n=int(input())
    a=list(map(int,input().split()))
    newa=list(set(a))
    if len(newa)==1:
        print(newa[0]*2)
    elif len(newa)==2:
        print(sum(newa))
    else:
        newa.sort()
        m1=newa.pop()
        m2=newa.pop()
        gcd=newa[0]
        for i in range(1,len(newa)):
            gcd=math.gcd(gcd,newa[i])
            if gcd==1:
                break
        s1=math.gcd(gcd,m1)
        s2=math.gcd(gcd,m2)
        print(max(s1+m2,s2+m1))


# cook your dish here
import math 
for _ in range(int(input())):
    n=int(input())
    a=list(map(int,input().split()))
    newa=list(set(a))
    if len(newa)==1:
        print(newa[0]*2)
    elif len(newa)==2:
        print(sum(newa))
    else:
        newa.sort()
        m1=newa.pop()
        m2=newa.pop()
        gcd=newa[0]
        for i in range(1,len(newa)):
            gcd=math.gcd(gcd,newa[i])
            if gcd==1:
                break
        s1=math.gcd(gcd,m1)
        s2=math.gcd(gcd,m2)
        print(max(s1+m2,s2+m1))


# cook your dish here
import math 
for _ in range(int(input())):
    n=int(input())
    a=list(map(int,input().split()))
    newa=list(set(a))
    if len(newa)==1:
        print(newa[0]*2)
    elif len(newa)==2:
        print(sum(newa))
    else:
        newa.sort()
        m1=newa.pop()
        m2=newa.pop()
        gcd=newa[0]
        for i in range(1,len(newa)):
            gcd=math.gcd(gcd,newa[i])
            if gcd==1:
                break
        s1=math.gcd(gcd,m1)
        s2=math.gcd(gcd,m2)
        print(max(s1+m2,s2+m1))
#import math as m
# for _ in range(int(input())):
#     length = int(input())
#     arr = list(map(int,input().split()))
#     if (length==2):
#         print(arr[0]+arr[1])
#     else:
#         tmparr=list(set(arr))
#         tmparr.sort()
#         fmax =tmparr.pop()
#         smax=tmparr.pop()
#         p = len(tmparr)
#         if (p==0):
#             print(fmax+smax)
#         else: 
#             result = tmparr[0]
#             for i in range(1,p):
#                 result = m.gcd(tmparr[i],result)
#             gcd0 = result
#             gcdH = m.gcd(gcd0,fmax)
#             gcdSH = m.gcd(gcd0,smax)
#             case11 = fmax+gcdSH
#             case22 = smax+gcdH
#             print(max(case11,case22))


# cook your dish here
import math as m
# for _ in range(int(input())):
#     n=int(input())
#     a=list(map(int,input().split()))
#     newa=list(set(a))
#     if len(newa)==1:
#         print(newa[0]*2)
#     elif len(newa)==2:
#         print(sum(newa))
#     else:
#         newa.sort()
#         m=newa.pop()
#         gcd=newa[0]
#         for i in range(1,len(a)):
#             gcd=math.gcd(gcd,a[i])
#             if gcd==1:
#                 break
#         print(m+gcd)

for _ in range(int(input())):
    length = int(input())
    arr = list(map(int,input().split()))
    if (length==2):
        print(arr[0]+arr[1])
    else:
        tmparr=list(set(arr))
        tmparr.sort()
        fmax =tmparr.pop()
        smax=tmparr.pop()
        p = len(tmparr)
        if (p==0):
            print(fmax+smax)
        else: 
            result = tmparr[0]
            for i in range(1,p):
                result = m.gcd(tmparr[i],result)
            gcd0 = result
            gcdH = m.gcd(gcd0,fmax)
            gcdSH = m.gcd(gcd0,smax)
            case11 = fmax+gcdSH
            case22 = smax+gcdH
            print(max(case11,case22))


import math
for i in range(int(input())):
    n=int(input())
    a=list(map(int,input().split()))
    if  len(set(a))==1:
        print(2*a[0])
    else:
        a=list(set(a))
        x,p=0,0
        z=max(a)
        a.remove(z)
        for i in range(len(a)):
            x=math.gcd(x,a[i])

        y=max(a)
        a.append(z)
        a.remove(y)
        for i in range(len(a)):
            p=math.gcd(p,a[i])
        print(max(z+x,p+y))

from math import gcd
def gh(a,b):
    if len(a) and len(b):
        x=a[0]
        y=b[0]
        for i in a[1:]:
            x=gcd(x,i)
        for i in b[1:]:
            y=gcd(y,i)
        return x+y
    return 0
def abc(l):
    s=2**len(l)
    i=0
    d="{0:0"+str(len(l))+"b}"
    ans=0
    while i<s:
        x=d.format(i)
        a=[]
        b=[]
        for j in range(len(l)):
            if x[j]=='1':
                a.append(l[j])
            else:
                b.append(l[j])
        ans=max(ans,gh(a,b))
        i+=1
    return ans
                
import random    
for _ in range(int(input())):
    n=int(input())
    l=list(map(int,input().split()))
    #
    d={}
    for i in l:
        try:
            d[i]+=1
        except:
            d[i]=1
    x=list(d.keys())
    x.sort()
    if len(x)==1:
        print(2*l[0])
    else:
        ans=x[-1]
        c=x[0]
        for i in range(len(x)-1):
            c=gcd(c,x[i])
        vy=ans+c
        ans=x[-2]
        c=0
        for i in range(len(x)-2):
            c=gcd(c,x[i])
        c=gcd(c,x[-1])
        vx=ans+c
        print(max(vx,vy))
            
    


import math

def __starting_point():
    for _ in range(int(input())):
        n=int(input())
        a=list(set(map(int, input().split())))
        n=len(a)
        flag=0
        if n==1:
            print(a[0]*2)
        else:
            Lgcd=[0]
            Rgcd=[0]
            for i in range(n):
                gcd=math.gcd(Lgcd[i],a[i])
                Lgcd.append(gcd)
            a=a[::-1]
            for i in range(n):
                gcd=math.gcd(Rgcd[i],a[i])
                Rgcd.append(gcd)
            Rgcd=Rgcd[::-1]
          
            a=a[::-1]
            ans=[]
            for i in range(n):
                gcd=a[i] + math.gcd(Lgcd[i],Rgcd[i+1])
                ans.append(gcd)
           # print(ans)
            print(max(ans))
            
            
                
            
                





__starting_point()

# cook your dish here
def gcd(x, y): 
    while(y): 
        x, y = y, x % y 
    return x 
def gcdlist(l):
    if(len(l)== 1):
        return l[0]
    else:
        num1 = l[0] 
        num2 = l[1] 
        gcdfinal = gcd(num1, num2) 
        for i in range(2, len(l)): 
            gcdfinal = gcd(gcdfinal, l[i]) 
        return(gcdfinal)
for i in range(int(input())):
    n = int(input())
    a = list(map(int,input().split()))
    if(n==1):
        print(a[0])
    elif(n == 2):
        print(a[0]+a[1])
    else :
        max1 = 0 
        max2 = 0 
        for i in range(1,n):
            if (a[i] > max1):
                max2 = max1 
                max1 = a[i] 
            elif (a[i] >max2 and a[i] !=max1) :
                max2= a[i]
        a1 = []
        a2 = []
        for i in range(n):
	        if(a[i] != max1 ):
	            a1.append(a[i])
	        if (a[i] != max2):
	            a2.append(a[i])
        if ( len(a1)== 0 ):
	        print(a[0])
        else :
            g1=gcdlist(a1)
            g2 = gcdlist(a2)
            print(max(g1 + max1 ,g2+max2))
	    
            
            
            

import math
for i in range(int(input())):
    n=int(input())
    a=list(map(int,input().split()))
    if  len(set(a))==1:
        print(2*a[0])
    else:
        a=list(set(a))
        x,p=0,0
        z=max(a)
        a.remove(z)
        for i in range(len(a)):
            x=math.gcd(x,a[i])

        y=max(a)
        a.append(z)
        a.remove(y)
        for i in range(len(a)):
            p=math.gcd(p,a[i])
        print(max(z+x,p+y))

# cook your dish here
import math
for _ in range(int(input())):
    n=int(input())
    a=list(map(int,input().split()))
    if  len(set(a))==1:
        print(2*a[0])
    else:
        a=list(set(a))
        x,p=0,0
        z=max(a)
        a.remove(z)
        for i in range(len(a)):
            x=math.gcd(x,a[i])

        y=max(a)
    ##print(y)
        a.append(z)
        a.remove(y)
        for i in range(len(a)):
            p=math.gcd(p,a[i])
        print(max(z+x,p+y))

# cook your dish here
import math
for _ in range(int(input())):
    n=int(input())
    a=list(map(int,input().split()))
    a=list(set(a))
    x,p=0,0
    z=max(a)
    a.remove(z)
    for i in range(len(a)):
        x=math.gcd(x,a[i])

    y=max(a)
    ##print(y)
    a.append(z)
    a.remove(y)
    for i in range(len(a)):
        p=math.gcd(p,a[i])
    print(max(z+x,p+y))


def gcd(a,b):
    if b==0:
        return a
    else:
        return gcd(b,a%b)


t=int(input())
for _ in range(t):
    n=int(input())
    l=list(map(int,input().split()))
    l=list(set(l))
    n=len(l)
    if(len(l)==1):
        print(l[0]*2)
        continue
    p=[0 for x in range(n)]
    s=[0 for x in range(n)]
    ans1=0
    p[0]=l[0]
    for i in range(1,n):
        p[i]=gcd(l[i],p[i-1])
    s[n-1]=l[n-1]
    for i in range(n-2,-1,-1):
        s[i]=gcd(l[i],s[i+1])
    #print(p)
    #print(s)
    for i in range(n):
        if(i==0):
            ans=s[i+1]+l[0]
        elif(i==n-1):
            ans=p[n-2]+l[n-1]
        else:
            ans=gcd(p[i-1],s[i+1])+l[i]
        #print(ans)
        ans1=max(ans1,ans)
    print(ans1)
    

def gcd(a,b):
    if b==0:
        return a
    else:
        return gcd(b,a%b)


t=int(input())
for _ in range(t):
    n=int(input())
    l=list(map(int,input().split()))
    l=list(set(l))
    n=len(l)
    if(len(l)==1):
        print(l[0]*2)
    p=[0 for x in range(n)]
    s=[0 for x in range(n)]
    ans1=0
    p[0]=l[0]
    for i in range(1,n):
        p[i]=gcd(l[i],p[i-1])
    s[n-1]=l[n-1]
    for i in range(n-2,-1,-1):
        s[i]=gcd(l[i],s[i+1])
    #print(p)
    #print(s)
    for i in range(n):
        if(i==0):
            ans=s[i+1]+l[0]
        elif(i==n-1):
            ans=p[n-2]+l[n-1]
        else:
            ans=gcd(p[i-1],s[i+1])+l[i]
        #print(ans)
        ans1=max(ans1,ans)
    print(ans1)
    

from math import gcd
for _ in range(int(input())):
    input()
    li=sorted(list(set(list(int(i) for i in input().split()))))
    if len(li)==1:print(2*li[0])
    elif len(li)==2:print(sum(li))
    else:
        g=li[0]
        for i in range(1,len(li)-2):g=gcd(li[i],g)
        m=gcd(g,li[-2])+li[-1]
        n=gcd(g,li[-1])+li[-2]
        print(max(m,n))

import math
t=int(input())
for _ in range (t) :
    n=int(input())
    arr=[int(x)for x in input().split()]
    arr=list(dict.fromkeys(arr))
    arr.sort(reverse=True)
    if(len(arr)==1) :
        ans=2*arr[0]
        print(ans)
        continue
    n=len(arr)
    b=arr[0]
    c=arr[1]
    if(n>=3) :
        temp=arr[2]
        for i in range (2, n) :
            temp=math.gcd(temp,arr[i])
        bval=math.gcd(b,temp)
        cval=math.gcd(c,temp)
        ans=max(bval+c , b+cval)
    else :
        ans=b+c
    print(ans)
    


# cook your dish here
# cook your dish here
hm={}
def gcd(a,b):
    if b>a:
        a,b=b,a
    if b==0:
        return a
    else:
        return gcd(b,a%b)
def gcd_list(l,n):
    gcd1=l[0]
    for i in range (1,n):
        gcd1=gcd(gcd1,l[i])
    return gcd1
        
for _ in range (int(input())):
    n=int(input())
    x=[int(n) for n in input().split()]
    l2=[]
    l=list(set(x))
    n=len(l)
    if n>2:
        hm={}
        temp=[]
        max1=max(l[0],l[1]) 
        max2=min(l[0],l[1]) 
        for i in range(2,len(l)): 
            if l[i]>max1: 
                max2=max1
                max1=l[i] 
            else: 
                if l[i]>max2: 
                    max2=l[i] 
        m1=max1
        m2=max2
        l.remove(m1)
        l.remove(m2)
        gcd_1=l[0]
        for i in range (1,n-2):
            gcd_1=gcd(gcd_1,l[i])
        s1=gcd(gcd_1,m2)+m1
        s2=gcd(gcd_1,m1)+m2
        print(max(s1,s2))
    else:
        if n==1:
            print(l[0]*2)
        else:
            print(sum(l))
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        

import math
def cal_gcd(a):
	first=a[0]
	for i in range(1,len(a)):
		first=math.gcd(first,a[i])

	return first

for _ in range(int(input())):
	n=int(input())
	a=list(set(map(int,input().split())))
	n=len(a)
	if(n==1):
		print(2*a[0])
	else:
		a.sort(reverse=True)
		b1=a[0]
		b2=a[1]
		if(n>=3):
			first=a[2]
			for i in range(3,len(a)):
				first=math.gcd(first,a[i])
			print(max(b1+math.gcd(first,b2), b2+math.gcd(first,b1)))
		else:
			print(b1+b2)