The $String$ Family gave birth to a new $Tripartite$ $trio$ $sisters$ and named them $Hema$, $Rekha$ and $Sushma$. Hema and Rekha are very fond of parties whereas Sushma hates them. One day Hema and Rekha asked their parents to buy them candies to distribute to people in their birthday party. (Remember Hema, Rekha and Sushma were born on the same day). But Sushma was uninterested in the party and only wanted candies for herself.
You will be given a list $P$ of possible number of candidates coming to the party. Were $P[i]$ denotes the count of people coming in the i th possibility. In each case every person should get maximum possible equal number of candies  such that after distributing the candies, there are always $R$ candies remaining for Sushma. You have to calculate the minimum number of candies required to buy so that, in any possible situation of the given array, each person coming to party gets equal number of candies (at least 1 and maximum possible out of total) and there are always $R$ candies remaining for Sushma.

-----Input:-----
- First line will contain $T$, number of testcases. Then the testcases follow. 
- First line of each test case contain  $N$, number of possible count of people coming to party
- Next line contain $N$ spaced integers denoting the count of people 
- Next line contain $R$ the number of candies always remaining after maximum equal distribution

-----Output:-----
For each testcase, output in a single line answer, the minimum number of candies required to buy.

-----Constraints-----
- $1 \leq T \leq 100$
- $1 \leq N \leq 10^4$
- $1 \leq P[i] \leq 41$
- $0 \leq R < min(P[i])$

-----Sample Input:-----
1
2
2 3
1

-----Sample Output:-----
7

Difficulty: interview

Starter code:

Solutions:
from math import gcd
def compute_lcm(x, y):
    lcm = (x*y)//gcd(x,y)
    return lcm

def LCMofArray(a):
    lcm = a[0]
    for i in range(1,len(a)):
        lcm = lcm*a[i]//gcd(lcm, a[i])
    return lcm

for _ in range(int(input())):
    lens = int(input())
    arrs = [int(x) for x in input().split()]
    rest = int(input())
    print(LCMofArray(arrs) + rest)



def find_lcm(num1, num2): 
    if(num1>num2): 
        num = num1 
        den = num2 
    else: 
        num = num2 
        den = num1 
    rem = num % den 
    while(rem != 0): 
        num = den 
        den = rem 
        rem = num % den 
    gcd = den 
    lcm = int(int(num1 * num2)/int(gcd)) 
    return lcm 
    
for _ in range(int(input())):
    n=int(input())
    p=list(map(int,input().split()))
    r=int(input())
    num1 = p[0]
    num2 = p[1]
    lcm = find_lcm(num1, num2)
    for i in range(2, n):
        lcm = find_lcm(lcm, p[i]) 
    print(lcm+r)

# cook your dish here
def hcf(x, y):
   if x > y:
       smaller = y
   else:
       smaller = x
   for i in range(1,smaller + 1):
       if((x % i == 0) and (y % i == 0)):
           hcf = i
   return hcf
l=[]
for _ in range(int(input())):
    n=int(input())
    a=list(map(int,input().split()))
    r=int(input())
    s=a[0]
    for i in range(1,n):
        s=(s*a[i])//hcf(s,a[i])
    l.append(s+r)
for i in l:
    print(i)

def listLCM(l):
    ans = 1
    for i in l:
        ans = lcm(ans,i)
    return ans
def lcm(a,b): 
    return (a*b) / gcd(a,b)

def gcd(a,b): 
    if a == 0: 
        return b 
    return gcd(b % a, a)

tc = int(input())
for _ in range(tc):
    people = int(input())
    candidates = list(set(map(int,input().split())))
    resh = int(input())
    print(int(listLCM(candidates))+resh, end = ' ')


import math 
  
def lcm (s, s1): 
    mul = s * s1 
    gcd = math.gcd(s, s1) 
    lcm = mul // gcd 
    return lcm 
  
# Driver Code 
def __starting_point(): 
  
    t=int(input()) #take the size
    while(t>0):
        t = t-1;
        N=int(input()) #take the size
        num_array=list(map(int, input().split(' ')[:N]))
        #for i in range(N):
            #n = int(input())
            #num_array[i] = n
        l = num_array[0]
        for i in range(1, N):
            l = lcm(l, num_array[i])
        r = int(input())
        print(l+int(r)) 
  

__starting_point()

# cook your dish here
# Python Program to find LCM of n elements 

def find_lcm(num1, num2): 
	if(num1>num2): 
		num = num1 
		den = num2 
	else: 
		num = num2 
		den = num1 
	rem = num % den 
	while(rem != 0): 
		num = den 
		den = rem 
		rem = num % den 
	gcd = den 
	lcm = int(int(num1 * num2)/int(gcd)) 
	return lcm 
t=int(input())
for _ in range(t):
    n=int(input())
    l = list(map(int,input().split()))
    r=int(input())
    

    num1 = l[0] 
    num2 = l[1] 
    lcm = find_lcm(num1, num2) 

    for i in range(2, len(l)): 
    	lcm = find_lcm(lcm, l[i]) 
	
    print(lcm+r) 




import sys


def find_lcm(num1, num2):
    if(num1 > num2):
        num = num1
        den = num2
    else:
        num = num2
        den = num1
    rem = num % den
    while(rem != 0):
        num = den
        den = rem
        rem = num % den
    gcd = den
    lcm = int(int(num1 * num2) / int(gcd))
    return lcm


t = int(sys.stdin.readline())
while t:
    n = int(sys.stdin.readline())
    l = list(map(int, sys.stdin.readline().split()))
    r = int(sys.stdin.readline())
    num1 = l[0]
    num2 = l[1]
    lcm = find_lcm(num1, num2)

    for i in range(2, len(l)):
        lcm = find_lcm(lcm, l[i])

    print(lcm + r)
    t -= 1


from math import gcd
n_case=int(input())
def LCMofArray(a):
  lcm = a[0]
  for i in range(1,len(a)):
    lcm = lcm*a[i]//gcd(lcm, a[i])
  return lcm

for _ in range(n_case):
    n=int(input())
    lt=list(set(map(int,input().split())))
    r=int(input())
    
    lcm=LCMofArray(lt)
    lcm+=r
    print(lcm)



# cook your dish here
import math
# function to calculate LCM
def LCMofArray(a):
       lcm = a[0]
       for i in range(1,len(a)):
              lcm = lcm*a[i]//math.gcd(lcm, a[i])
       return lcm
for T in range(int(input())):
       n=int(input())
       N=list(map(int,input().split()))
       r=int(input())
       print(LCMofArray(N)+r)


# cook your dish here

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

def lcm(x):
    ans=x[0]
    for i in range(1,len(x)):
        ans=(ans*x[i])//gcd(x[i],ans)
    return(ans)
    

t=int(input())
while t>0:
    t-=1
    n=int(input())
    x=list(map(int,input().split()))
    r=int(input())
    z=lcm(x)+r
    print(z)

def LCM(arr, n): 
      
   
    max_num = 0; 
    for i in range(n): 
        if (max_num < arr[i]): 
            max_num = arr[i]

    res = 1; 
  
    x=2
    while (x <= max_num): 
          

        indexes = []; 
        for j in range(n): 
            if (arr[j] % x == 0): 
                indexes.append(j)
  
        if (len(indexes) >= 2): 
              
            
            for j in range(len(indexes)): 
                arr[indexes[j]] = int(arr[indexes[j]] / x)
  
            res = res * x
        else: 
            x += 1; 
  
  
    for i in range(n): 
        res = res * arr[i]
        
  
    return res+r
t=int(input())
for i in range(0,t):

    n=int(input())
    arr=list(map(int,input().split()))
    r=int(input())
    print(LCM(arr, n))
    
    



def lcm(a,b):
    if(a>b): 
        num = a 
        den = b 
    else: 
        num = b 
        den = a
    rem = num % den 
    while(rem != 0): 
        num = den 
        den = rem 
        rem = num % den 
    gcd = den 
    x = int(int(a * b)/int(gcd)) 
    return x

for _ in range(int(input())):
    n=int(input())
    p=list(map(int,input().split()))
    r=int(input())
    if n==1:
        print(p[0]+r)
    else:
        ans=lcm(p[0],p[1])
        for i in range(2,n):
            ans=lcm(ans,p[i])
        print(ans+r)


def op_lcm(nm1, nm2): 
	if(nm1>nm2): 
		nm = nm1 
		den = nm2 
	else: 
		nm = nm2 
		den = nm1 
	rem = nm % den 
	while(rem != 0): 
		nm = den 
		den = rem 
		rem = nm % den 
	gcd = den 
	lcm = int(int(nm1 * nm2)/int(gcd)) 
	return lcm 

t=int(input())
while t>0:
	t-=1
	n=int(input())
	l=list(map(int,input().split()))
	r=int(input())
	nm1 = l[0] 
	nm2 = l[1] 
	lcm = op_lcm(nm1, nm2) 

	for i in range(2, len(l)): 
		lcm = op_lcm(lcm, l[i]) 
		
	print(lcm+r) 


	


from math import gcd
for _ in range(int(input())):
    n = int(input())
    p = list(map(int,input().split()))
    r = int(input())
    lcm = p[0]
    for i in p[1:]:
      lcm = int(lcm*i/gcd(lcm, i))
    print(int(lcm+r))

from math import gcd
for _ in range(int(input())):
    n = int(input())
    p = list(map(int,input().split()))
    r = int(input())
    lcm = p[0]
    for i in p[1:]:
      lcm = int(lcm*i/gcd(lcm, i))
    print(int(lcm+r))

# cook your dish here
from math import gcd
for _ in range(int(input())):
    N = int(input())
    lst = list(map(int,input().split()))
    R = int(input())
    lcm = lst[0]
    
    for i in lst[1:]:
      lcm = lcm*(i//(gcd(lcm, i)))
    print(lcm+R)

# Python Program to find LCM of n elements 

def find_lcm(num1, num2): 
	if(num1>num2): 
		num = num1 
		den = num2 
	else: 
		num = num2 
		den = num1 
	rem = num % den 
	while(rem != 0): 
		num = den 
		den = rem 
		rem = num % den 
	gcd = den 
	lcm = int(int(num1 * num2)/int(gcd)) 
	return lcm 
for j in range(int(input())):
    n=int(input())
    l =list(map(int,input().split())) 
    x=int(input())
    num1 = l[0] 
    num2 = l[1] 
    lcm = find_lcm(num1, num2) 
    for i in range(2, len(l)):
        lcm = find_lcm(lcm, l[i])
    lcm+=x
    print(lcm)
	
 

# Code contributed by Mohit Gupta_OMG 


import math
def LCM(a):
  lcm = a[0]
  for i in range(1,len(a)):
    lcm = lcm*a[i]//math.gcd(lcm, a[i])
  return lcm

t=int(input())
for _ in range(t):
    n=int(input())
    guest=list(map(int,input().split()))
    r=int(input())
    lcm=LCM(guest)
    print(lcm+r)


from math import gcd


def LCM(a):
  lcm = a[0]
  for i in range(1,len(a)):
    lcm = lcm*a[i]//gcd(lcm, a[i])
  return lcm



t = int(input())
while t>0:
    n = int(input())
    lst = list(map(int,input().split()))
    r = int(input())

    res = LCM(lst)

    print(res + r)

    t-=1

import math

def LCM(a):
  lcm = a[0]
  for i in range(1,len(a)):
    lcm = lcm*a[i]//math.gcd(lcm, a[i])
  return lcm

t=int(input())
for _ in range(t):
    n=int(input())
    guest=list(map(int,input().split()))
    r=int(input())
    lcm=LCM(guest)
    print(lcm+r)


# cook your dish here
def find_lcm(num1, num2): 
    if(num1>num2): 
        num = num1 
        den = num2 
    else: 
        num = num2 
        den = num1 
    rem = num % den 
    while(rem != 0): 
        num = den 
        den = rem 
        rem = num % den 
    gcd = den 
    lcm = int(int(num1 * num2)/int(gcd)) 
    return lcm 

for _ in range(int(input())):
    n=int(input())
    l=list(map(int,input().split()))
    r=int(input())

    num1 = l[0] 
    num2 = l[1] 
    lcm = find_lcm(num1, num2) 
    for i in range(2, len(l)): 
        lcm = find_lcm(lcm, l[i]) 
    print(lcm+r) 



import math

def lcm(a):
  lm = a[0]
  for i in range(1,len(a)):
    lm = lm*a[i]//math.gcd(lm, a[i])
  return lm
	
t = int(input())
for T in range(t):
	n = int(input())
	l = list(map(int,input().split()))
	r = int(input())
	lc = lcm(l)
	print(lc+r)


def gcd(a,b): 
    if a == 0: 
        return b 
    return gcd(b % a, a) 

# Function to return LCM of two numbers 
def lcm(a): 
    res = 1
    for i in range(len(a)):
      res = res*a[i]//gcd(res,a[i])
    return res

for _ in range(int(input())):
  n = int(input())
  p = list(map(int,input().split()))
  r = int(input())
  print(lcm(p)+r)

# cook your dish here
def gcd(a,b): 
    if a == 0: 
        return b 
    return gcd(b % a, a) 
  
def lcm(a,b): 
    return (a*b) // gcd(a,b) 
 
for _ in range(int(input())) :
    n = int(input())
    arr = list(map(int , input().split()))
    k = int(input())
    if(n==1) :
        print(arr[0]+k)
    if(n==2) :
        print(lcm(arr[0],arr[1])+k)
    else :
        l = lcm(arr[0],arr[1])
        for i in range(2, len(arr)): 
            l = lcm(l, arr[i])
        print(l+k)

import math

# function to calculate LCM
def L(a):
  lcm = a[0]
  for i in range(1,len(a)):
    lcm = lcm*a[i]//math.gcd(lcm, a[i])
  return lcm
  
for _ in range(int(input())):
    n=int(input())
    l=list(map(int,input().split()))
    r=int(input())
    c=L(l)
    print(c+r)