Diana is planning to make a very long journey. Her journey consists of $N$ bus routes, numbered from $1 to N$ in the order she must take them. The buses themselves are very fast but do not run often. The $i-th$ bus route only runs every $Xi$ days.

More specifically, she can only take the $i-th$ bus on day $Xi, 2Xi, 3Xi$, and so on. Since the buses are very fast, she can take multiple buses on the same day.

Diana must finish her journey by day D, but she would like to start the journey as late as possible. What is the latest day she could take the first bus, and still finish her journey by day $D$?
It is guaranteed that it is possible for Diana to finish her journey by day $D$.  

-----Input:-----
The first line of the input gives the number of test cases, $T$. $T$ test cases follow. Each test case begins with a line containing the two integers N and D. Then, another line follows containing $N$ integers, the $i-th$ one is $Xi$.

-----Output:-----
For each test case, output one line containing an integer $Y$, where $Y$ is the latest day she could take the first bus, and still finish her journey by day $D$.

-----Constraints-----
- $1 \leq T \leq 100$
- $1 \leq Xi \leq D.$
- $1 \leq N \leq 1000.$
It is guaranteed that it is possible for Diana to finish her journey by day $D$.

-----Sample Input:-----
3

3 10

3 7 2

4 100

11 10 5 50

1 1

1  

-----Sample Output:-----
6  

99

1  

-----EXPLANATION:-----
In Sample $Case 1$, there are $N = 3$ bus routes and Bucket must arrive by day $D = 10$. She could:
- Take the 1st bus on day 6 $(X1 = 3)$,
- Take the 2nd bus on day 7 $(X2 = 7)$ and
- Take the 3rd bus on day 8 $(X3 = 2)$.  
In Sample $Case 2$, there are $N = 4$ bus routes and Bucket must arrive by day $D = 100$. She could:
- Take the 1st bus on day 99 $(X1 = 11)$,
- Take the 2nd bus on day 100$ (X2 = 10)$,
- Take the 3rd bus on day 100 $(X3 = 5)$ and
- Take the 4th bus on day 100 $(X4 = 50)$,  
In Sample Case 3, there is $N = 1$ bus route, and Bucket must arrive by day $D = 1$. She could:
- Take the 1st bus on day 1 $(X1 = 1)$.

Difficulty: interview

Starter code:

Solutions:
t = int(input())
for _ in range(t):
    nd = list(map(int, input().split()))
    n = nd[0]
    d = nd[1]
    cutOff = []
    x = d
    buses = list(map(int, input().split()))
    for i in range(len(buses)-1,-1,-1):
        x = x - x%buses[i]
    print(x)











            



t = int(input())
for _ in range(t):
    nd = list(map(int, input().split()))
    n = nd[0]
    d = nd[1]
    cutOff = []
    x = d
    buses = list(map(int, input().split()))
    for i in range(len(buses)-1,-1,-1):
        x = x - x%buses[i]
    print(x)











            



cases=int(input())
for i in range(cases):
    n,days=map(int,input().split())
    buses=list(map(int,input().split()))
    buses.reverse()
    for j in buses:
        days=days-(days%j)
    print(days)

# cook your dish here
try:
    for _ in range(int(input())):
        n,d=[int(i) for i in input().split()]
        a=[int(i) for i in input().split()]
        i=n-1
        r=d
        while i>=0:
            r=(r//a[i])*a[i]
            i-=1 
        print(r)
except EOFError as error:
    pass


# cook your dish here
try:
    for _ in range(int(input())):
        n,d=[int(i) for i in input().split()]
        a=[int(i) for i in input().split()]
        i=n-1
        r=d
        while i>=0:
            r=(r//a[i])*a[i]
            i-=1 
        print(r)
except EOFError as error:
    pass


# cook your dish here
try:
    for _ in range(int(input())):
        n,d=[int(i) for i in input().split()]
        a=[int(i) for i in input().split()]
        i=n-1
        r=d
        while i>=0:
            r=(r//a[i])*a[i]
            i-=1 
        print(r)
except EOFError as error:
    pass


# cook your dish here
try:
    for _ in range(int(input())):
        n,d=[int(i) for i in input().split()]
        a=[int(i) for i in input().split()]
        i=n-1
        r=d
        while i>=0:
            r=(r//a[i])*a[i]
            i-=1 
        print(r)
except EOFError as error:
    pass


# cook your dish here
try:
    x=int(input())
    for _ in range(x):
        b=list(map(int,input().split()))
        a=list(map(int,input().split()))
        y=b[1]
        j=len(a)-1
        while j>=0:
            y=a[j]*int(y/a[j])
            j-=1
        print(y)
except:
    pass

# cook your dish here
from sys import stdin,stdout,setrecursionlimit
from math import ceil

t = int(stdin.readline())
for _ in range(t):
    n,d = list(map(int,input().split()))
    a = list(map(int,input().split()))
    c = a[:]
    
    for i in range(n):
        q = d // a[i]
        a[i] *= q 
    for i in range(n-1,0,-1):
        if a[i] - a[i-1] < 0:
            q = a[i] // c[i-1]
            a[i-1] = c[i-1] * q
        elif a[i] - a[i-1] > 1:
            q = a[i-1] // c[i]
            a[i] = c[i]*(q+1)
            
    print(a[0])       
        
            
        
    


#

def getAns(d, arr):
    latestDate = 0
    tempToMatch = d
    for ele in arr:
        latestDate = ele * (tempToMatch // ele)
        tempToMatch = latestDate
    return latestDate




def __starting_point():
    t = int(input())
    for _ in range(t):
        N, D = input().split()
        Arr = list(map(int, input().strip().split()))
        print(getAns(int(D), Arr[::-1]))
__starting_point()

for _ in range(int(input())):
    n,d=map(int,input().split())
    a=list(map(int,input().split()))


    for i in range(n-1,-1,-1):

        ans=(d//a[i])
        ans1=ans*a[i]
        mini=ans1
        d=ans1
        ##p##rint(mini,d)
    print(mini)

for _ in range(int(input())):
    n, d = map(int, input().split())
    arr = list(map(int, input().split()))

    
    for i in range(n):
        item = arr[n-1-i]
        d = (d//item )* item
    print(d)

# cook your dish here
for i in range(int(input())):
    n, d = map(int, input().split())
    a = [int(x) for x in input().split()]
    b = []
    for t in reversed(range(n)):
        x = d//a[t]
        b.append(x*a[t])
        d = x*a[t]
        
    print(min(b))

for _ in range(int(input())):
    n,d=list(map(int,input().split()))
    l=list(map(int,input().split()))
    l=l[::-1]
    
    for i in l:
        d=(d//i)*i
    print(d)


for _ in range(int(input())):
    N, D = map(int, input().split())
    R = list(map(int, input().split()))
    
    Cur = D
    for i in range(N-1, -1, -1):
        if (i == (N-1)):
            T = Cur//R[i]
            R[i] = R[i]*T
            Cur = R[i]
        else:
            T = Cur//R[i]
            R[i] = R[i]*T
            Cur = R[i]
    
    print(Cur)

# cook your dish here
t = int(input())
for _ in range(t):
    n, d = list(map(int, input().split()))
    days = list(map(int, input().split()))
    x = d
    for i in range(n-1, -1, -1):
        x = x // days[i] * days[i]
    print(x)     
            

            
            


for _ in range(int(input())):
    n,d=list(map(int,input().split()))
    l=list(map(int,input().split()))
    i=n-1
    cv=d
    while(i>=0):
        q=cv//l[i]
        cv=l[i]*q
        i-=1
    print(cv)





# cook your dish here
t = int(input())
for _ in range(t):
    n, d = list(map(int, input().split()))
    days = list(map(int, input().split()))
    x = d
    for i in range(n-1, -1, -1):
        x = x // days[i] * days[i]
    print(x)     
            

            
            


# cook your dish here
def possible(l,n,k):
    pass
def bs(l,n,d):
    i=1
    j=d
    ans=1
    while i<=j:
        mid = i+(j-i)//2
        if possible(l,n,mid):
            ans=mid
            i=mid+1
        else:
            j=mid-1
    return ans
t=int(input())
for _ in range(t):
    n,d=list(map(int,input().split()))
    l=list(map(int,input().split()))
    #print(bs(l,n,d))
    #k=[]
    for j in l[::-1]:
        c=d//j
        d=c*j

    print(d)


# cook your dish here
for u in range(int(input())):
    n,k=list(map(int,input().split()))
    l=list(map(int,input().split()))
    for i in range(n-1,-1,-1):
        r=k//l[i]
        k=r*l[i]
    print(k)


#dt = {} for i in x: dt[i] = dt.get(i,0)+1
import sys;input = sys.stdin.readline
inp,ip = lambda :int(input()),lambda :[int(w) for w in input().split()]

for _ in range(1,int(input())+1):
    n,d = map(int,input().split())
    x = [int(w) for w in input().split()]
    ans = []
    ans.append(x[-1]*(d//x[-1]))
    prev = ans[0]
    for i in reversed(range(n-1)):
        ans.append(x[i]*(prev//x[i]))
        prev = ans[-1]
    print(min(ans))