CodeEff/ECCO huggingface dataset:
# Original solution
import sys
readline = sys.stdin.readline
INF = int(1e10)
def merge(A, left, mid, right):
    L = A[left: mid] + [[0, INF]]
    R = A[mid: right] + [[0, INF]]
    i = j = 0
    for k in range(left, right):
        if L[i][1] <= R[j][1]:
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1
def mergeSort(A, left, right):
    if left + 1 < right:
        mid = (left + right) // 2
        mergeSort(A, left, mid)
        mergeSort(A, mid, right)
        merge(A, left, mid, right)
def partition(A, p, r):
    x = A[r][1]
    i = p - 1
    for j in range(p, r):
        if A[j][1] <= x:
            i += 1
            A[i], A[j] = A[j], A[i]
    A[i + 1], A[r] = A[r], A[i + 1]
    return i + 1
def quicksort(A, p, r):
    if p < r:
        q = partition(A, p, r)
        quicksort(A, p, q - 1)
        quicksort(A, q + 1, r)
n = int(input())
f = lambda a: (a[0], int(a[1]))
A = [f(readline().split()) for _ in range(n)]
B = A[:]
mergeSort(A, 0, n)
quicksort(B, 0, n - 1)
print("Stable" if A == B else "Not stable")
print(*(f"{a} {b}" for a, b in B), sep="\n")



# Optimized solution
import sys
readline = sys.stdin.readline
import sys
readline = sys.stdin.readline
INF = int(1e10)
def partition(A, p, r):
    x = A[r][1]
    i = p - 1
    for j in range(p, r):
        if A[j][1] <= x:
            i += 1
            A[i], A[j] = A[j], A[i]
    A[i + 1], A[r] = A[r], A[i + 1]
    return i + 1
def quicksort(A, p, r):
    if p < r:
        q = partition(A, p, r)
        quicksort(A, p, q - 1)
        quicksort(A, q + 1, r)
def isStable(A):
    for i in range(0, len(A) - 1):
        if A[i][1] == A[i + 1][1]:
            if A[i][2] > A[i + 1][2]:
                return False
    return True
n = int(input())
f = lambda a, i: (a[0], int(a[1]), i)
A = [f(readline().split(), i) for i in range(n)]
quicksort(A, 0, n - 1)
print("Stable" if isStable(A) else "Not stable")
print(*(f"{a} {b}" for a, b, c in A), sep="\n")
# Original solution
import sys
readline = sys.stdin.readline
import sys
readline = sys.stdin.readline
INF = int(1e10)
def partition(A, p, r):
    x = A[r][1]
    i = p - 1
    for j in range(p, r):
        if A[j][1] <= x:
            i += 1
            A[i], A[j] = A[j], A[i]
    A[i + 1], A[r] = A[r], A[i + 1]
    return i + 1
def quicksort(A, p, r):
    if p < r:
        q = partition(A, p, r)
        quicksort(A, p, q - 1)
        quicksort(A, q + 1, r)
def isStable(A):
    for i in range(0, len(A) - 1):
        if A[i][1] == A[i + 1][1]:
            if A[i][2] > A[i + 1][2]:
                return False
    return True
n = int(input())
f = lambda a, i: (a[0], int(a[1]), i)
A = [f(readline().split(), i) for i in range(n)]
quicksort(A, 0, n - 1)
print("Stable" if isStable(A) else "Not stable")
print(*(f"{a} {b}" for a, b, c in A), sep="\n")



# Optimized solution
import sys
readline = sys.stdin.readline
def partition(A, p, r):
    x = A[r][1]
    i = p - 1
    for j in range(p, r):
        if A[j][1] <= x:
            i += 1
            A[i], A[j] = A[j], A[i]
    A[i + 1], A[r] = A[r], A[i + 1]
    return i + 1
def quicksort(A, p, r):
    if p < r:
        q = partition(A, p, r)
        quicksort(A, p, q - 1)
        quicksort(A, q + 1, r)
def isStable(A):
    for i in range(0, len(A) - 1):
        if A[i][1] == A[i + 1][1]:
            if A[i][2] > A[i + 1][2]:
                return False
    return True
n = int(eval(input()))
f = lambda a, i: (a[0], int(a[1]), i)
A = [f(readline().split(), i) for i in range(n)]
quicksort(A, 0, n - 1)
print(("Stable" if isStable(A) else "Not stable"))
print(("\n".join(f"{a} {b}" for a, b, c in A)))
# Original solution
import sys
readline = sys.stdin.readline
def partition(A, p, r):
    x = A[r][1]
    i = p - 1
    for j in range(p, r):
        if A[j][1] <= x:
            i += 1
            A[i], A[j] = A[j], A[i]
    A[i + 1], A[r] = A[r], A[i + 1]
    return i + 1
def quicksort(A, p, r):
    if p < r:
        q = partition(A, p, r)
        quicksort(A, p, q - 1)
        quicksort(A, q + 1, r)
def isStable(A):
    for i in range(0, len(A) - 1):
        if A[i][1] == A[i + 1][1]:
            if A[i][2] > A[i + 1][2]:
                return False
    return True
n = int(eval(input()))
f = lambda a: (a[0], int(a[1]))
A = [f(readline().split()) + (i,) for i in range(n)]
quicksort(A, 0, n - 1)
print(("Stable" if isStable(A) else "Not stable"))
print(("\n".join(f"{a} {b}" for a, b, c in A)))



# Optimized solution
import sys
readline = sys.stdin.readline
def partition(A, p, r):
    x = A[r][1]
    i = p - 1
    for j in range(p, r):
        if A[j][1] <= x:
            i += 1
            A[i], A[j] = A[j], A[i]
    A[i + 1], A[r] = A[r], A[i + 1]
    return i + 1
def quicksort(A, p, r):
    if p < r:
        q = partition(A, p, r)
        quicksort(A, p, q - 1)
        quicksort(A, q + 1, r)
def isStable(A):
    for i in range(0, len(A) - 1):
        if A[i][1] == A[i + 1][1]:
            if A[i][2] > A[i + 1][2]:
                return "Not stable"
    return "Stable"
n = int(eval(input()))
f = lambda a, i: (a[0], int(a[1]), i)
A = [f(readline().split(), i) for i in range(n)]
quicksort(A, 0, n - 1)
print((isStable(A)))
print(("\n".join(f"{a} {b}" for a, b, c in A)))
# Original solution
INF = 10**10


def partition(ary, p, r):
    x = ary[r][1]
    i = p - 1
    for j in range(p, r):
        if ary[j][1] <= x:
            i += 1
            ary[i], ary[j] = ary[j], ary[i]

    ary[i + 1], ary[r] = ary[r], ary[i + 1]

    return i + 1


def quick_sort(ary, p, r):
    if p < r:
        q = partition(ary, p, r)
        quick_sort(ary, p, q - 1)
        quick_sort(ary, q + 1, r)


def merge(ary, left, mid, right):
    lry = ary[left:mid]
    rry = ary[mid:right]
    lry.append(('INF', INF))
    rry.append(('INF', INF))

    i = 0
    j = 0
    for k in range(left, right):
        if lry[i][1] <= rry[j][1]:
            ary[k] = lry[i]
            i += 1
        else:
            ary[k] = rry[j]
            j += 1

    return right - left


def merge_sort(ary, left, right):
    cnt = 0
    if left + 1 < right:
        mid = (left + right) // 2
        cnt += merge_sort(ary, left, mid)
        cnt += merge_sort(ary, mid, right)
        cnt += merge(ary, left, mid, right)

    return cnt


# if __name__ == '__main__':
import sys
from copy import deepcopy

n = int(input())
# ary = [(lambda x: (x[0], int(x[1])))(input().split()) for i in range(n)]

ary = [(lambda x: (x[0], int(x[1])))(line.strip().split()) for line in sys.stdin]

qary = deepcopy(ary)
mary = deepcopy(ary)
quick_sort(qary, 0, n - 1)
merge_sort(mary, 0, n)

if qary == mary:
    print('Stable')
else:
    print('Not stable')
[print(*_) for _ in qary]



# Optimized solution
INF = 10**10


def partition(ary, p, r):
    x = ary[r][1]
    i = p - 1
    for j in range(p, r):
        if ary[j][1] <= x:
            i += 1
            ary[i], ary[j] = ary[j], ary[i]

    ary[i + 1], ary[r] = ary[r], ary[i + 1]

    return i + 1


def quick_sort(ary, p, r):
    if p < r:
        q = partition(ary, p, r)
        quick_sort(ary, p, q - 1)
        quick_sort(ary, q + 1, r)


def merge(ary, left, mid, right):
    lry = ary[left:mid]
    rry = ary[mid:right]
    lry.append(('INF', INF))
    rry.append(('INF', INF))

    i = 0
    j = 0
    for k in range(left, right):
        if lry[i][1] <= rry[j][1]:
            ary[k] = lry[i]
            i += 1
        else:
            ary[k] = rry[j]
            j += 1

    return right - left


def merge_sort(ary, left, right):
    cnt = 0
    if left + 1 < right:
        mid = (left + right) // 2
        cnt += merge_sort(ary, left, mid)
        cnt += merge_sort(ary, mid, right)
        cnt += merge(ary, left, mid, right)

    return cnt


if __name__ == '__main__':
    import sys
    from copy import deepcopy

    n = int(input())
    ary = [(lambda x: (x[0], int(x[1])))(line.strip().split()) for line in sys.stdin]

    qary = deepcopy(ary)
    mary = deepcopy(ary)
    quick_sort(qary, 0, n - 1)
    merge_sort(mary, 0, n)

    if qary == mary:
        print('Stable')
    else:
        print('Not stable')
    [print(*_) for _ in qary]
# Original solution
def partition(A, p, r):
    x = int(A[r-1][1])
    i = p-1

    for j in range(p,r-1):
        if int(A[j][1]) <= x:
            i = i + 1
            A[i],A[j] = A[j],A[i]
    A[i+1],A[r-1] = A[r-1],A[i+1]
    return i + 1

def qsort(A,p,r):
    if p < r:
        q = partition(A,p,r)
        qsort(A,p,q)
        qsort(A,q+1,r)
    return A

def isStable(a, b):
    length = int(len(a))
    for i in range(length):
        for j in range(i+1,length-1) :
            for x in range(length):
                for y in range(x+1,length-1) :
                    if a[i][1]==a[j][1] and a[i] == b[y] and a[j] == b[x]:
                        return False
                        break
    return True

if __name__ == '__main__':
    cnt = int(eval(input()))
    A = []
    for i in range(cnt):
        A.append(input().split())
    A2 = A[:]
    p = 0
    r = len(A)
    B = qsort(A,p,r)
    if isStable(A2,B):
        print("Stable")
    else:
        print("Not stable")
    for i in B:
        print(("{0} {1}".format(i[0],i[1])))

# Optimized solution
def partition(A, p, r):
    x = int(A[r-1][1])
    i = p-1

    for j in range(p,r-1):
        if int(A[j][1]) <= x:
            i = i + 1
            A[i],A[j] = A[j],A[i]
    A[i+1],A[r-1] = A[r-1],A[i+1]
    return i + 1

def qsort(A,p,r):
    if p < r:
        q = partition(A,p,r)
        qsort(A,p,q)
        qsort(A,q+1,r)
    return A

def isStable(a):
    length = int(len(a))
    for i in range(length):
        for j in range(i+1,length-1) :
            if a[i][1] == a[j][1] and a[i][2] > a[j][2]:
                return False
                break
    return True

if __name__ == '__main__':
    cnt = int(eval(input()))
    A = []
    for i in range(cnt):
        N = input().split()
        N.append(i)
        A.append(N)
    p = 0
    r = len(A)
    B = qsort(A,p,r)
    if isStable(B):
        print("Stable")
    else:
        print("Not stable")
    for i in B:
        print(("{0} {1}".format(i[0],i[1])))
# Original solution
import sys
readline = sys.stdin.readline
readlines = sys.stdin.readlines

N = int(readline())
XY = [tuple(int(x) for x in line.split()) for line in readlines()]

graph = [[] for _ in range(N+1)]
for x,y in XY:
    graph[x].append(y)
    graph[y].append(x)

visited = [False] * (N+1)
visited[1] = True
q = [1]
ord = [1]
par = [0] * (N+1)
while q:
    x = q.pop()
    for y in graph[x]:
        if visited[y]:
            continue
        ord.append(y)
        par[y] = x
        visited[y] = True
        q.append(y)

G = [0] * (N+1)
for x in ord[::-1]:
    p = par[x]
    G[p] ^= (G[x]+1)

answer = 'Alice' if G[1] != 0 else 'Bob'
print(answer)

# Optimized solution
import sys
readline = sys.stdin.readline
readlines = sys.stdin.readlines

N = int(readline())
XY = (tuple(int(x)-1 for x in line.split()) for line in readlines())

graph = [[] for _ in range(N)]
for x,y in XY:
    graph[x].append(y)
    graph[y].append(x)

visited = [True] + [False] * (N-1)
q = [0]
ord = [0]
par = [0] * N
while q:
    x = q.pop()
    for y in graph[x]:
        if visited[y]:
            continue
        ord.append(y)
        par[y] = x
        visited[y] = True
        q.append(y)

G = [0] * (N+1)
for x in ord[:0:-1]:
    p = par[x]
    G[p] ^= (G[x]+1)

answer = 'Alice' if G[0] != 0 else 'Bob'
print(answer)
# Original solution
import sys

def solve():
    file_input = sys.stdin
    N, W = list(map(int, file_input.readline().split()))
    C = [0] * (W + 1)
    for line in file_input:
        item_v, item_w = list(map(int, line.split()))
        for i, sv in enumerate(C[:-item_w]):
            V = [v + item_v * j for j, v in enumerate(C[i + item_w::item_w], start=1)]
            C[i] = max(V + [sv])
    print((C[0]))

solve()

# Optimized solution
import sys

def solve():
    file_input = sys.stdin
    N, W = list(map(int, file_input.readline().split()))
    C = [0] * (W + 1)
    for line in file_input:
        item_v, item_w = list(map(int, line.split()))
        for i, vals in enumerate(zip(C, C[item_w:]), start=item_w):
            v1, v2 = vals
            C[i] = max(v1 + item_v, v2)
    print((C[W]))

solve()
# Original solution
import sys
readline = sys.stdin.readline

N, W = list(map(int, readline().split()))

dp = [0] * (W+1)

for i in range(N):
    item_v, item_w = list(map(int, readline().split()))
    for w in range(W-item_w+1):
        if dp[w+item_w] < dp[w] + item_v:
            dp[w+item_w] = dp[w] + item_v

print((max(dp)))

# Optimized solution
N, W = list(map(int, input().split()))
dp = [0]*(W+1)
for i in range(N):
    v, w = list(map(int, input().split()))
    for j in range(0, W-w+1):
        if dp[j+w] < dp[j] + v:
            dp[j+w] = dp[j] + v
print((max(dp)))
# Original solution
INF = 10 ** 12

N, W = list(map(int, input().split()))

items =[] * N

for i in range(N):
    v, w = list(map(int, input().split()))
    items.append([v,w])

dp = [[INF for i in range(W+1)] for j in range(N+1)]

for i in range(W+1):
    dp[0][i] = 0

for i in range(N+1):
    dp[i][0] = 0

for i in range(1,N+1): #1<= i <= N
    for j in range(1, W+1): # 1 <= j <= W
        if j - items[i-1][1] >= 0:
            dp[i][j] = max(dp[i-1][j], dp[i-1][j - items[i-1][1]] + items[i-1][0], dp[i][j - items[i-1][1]] + items[i-1][0])
        else:
            dp[i][j] = dp[i-1][j]

print((dp[N][W]))

# Optimized solution
def solve():
    
    INF = 10 ** 12
    
    N, W = list(map(int, input().split()))
    
    items =[] * N
    
    for i in range(N):
        v, w = list(map(int, input().split()))
        items.append([v,w])
    
    dp = [[INF for i in range(W+1)] for j in range(N+1)]
    
    for i in range(W+1):
        dp[0][i] = 0
    
    for i in range(N+1):
        dp[i][0] = 0
    
    for i in range(1,N+1): #1<= i <= N
        for j in range(1, W+1): # 1 <= j <= W
            if j - items[i-1][1] >= 0:
                dp[i][j] = max(dp[i-1][j], dp[i-1][j - items[i-1][1]] + items[i-1][0], dp[i][j - items[i-1][1]] + items[i-1][0])
            else:
                dp[i][j] = dp[i-1][j]
    
    print((dp[N][W]))

if __name__ == '__main__':
    solve()
# Original solution
import copy
length, cap = list(map(int, input().split(" ")))
dp = [0] * (cap + 1)
items = []
for _ in range(length):
    a, b = list(map(int, input().split(" ")))
    items.append([a, b])

for item in items:
    v, w = item
    temp_dp = copy.copy(dp)
    temp_dp[w] = max(temp_dp[w], v)
    for j in range(cap):
        if temp_dp[j] and w + j <= cap:
            temp_dp[w + j] = max(temp_dp[w + j], v + temp_dp[j])
    dp = temp_dp
answer = max(dp)
print(answer)


# Optimized solution
length, weight = list(map(int, input().split(" ")))
dp = [0 for n in range(weight + 1)]

for i in range(length):
    v, w = list(map(int, input().split(" ")))

    dp[w] = max(v, dp[w])
    for j in range(weight):
        if dp[j] and j + w <= weight:
            dp[j + w] = max(dp[j] + v, dp[j + w])

print((max(dp)))
# Original solution
N,W=list(map(int,input().split()))
vw=[list(map(int,input().split())) for i in range(N)]
dp=[[0]*(W+1) for _ in range(N+1)]
for i in range(N):
    for j in range(W+1):
        if vw[i][1]>j:
            dp[i+1][j]=dp[i][j]
        else:
            dp[i+1][j]=max(dp[i][j],dp[i+1][j-vw[i][1]]+vw[i][0])
print((dp[N][W]))

# Optimized solution
n,w=list(map(int,input().split()))
vw=[list(map(int,input().split())) for _ in range(n)]
dp=[0]*(w+1)
for i in range(n):
    for j in range(vw[i][1],w+1):
        dp[j]=max(dp[j],dp[j-vw[i][1]]+vw[i][0])
print((dp[w]))
# Original solution
n,w = list(map(int, input().split()))
values = [0]
weights = [0]
counter=0
for i in range(n):
    v,weight = list(map(int, input().split()))
    values.append(v)
    weights.append(weight)

for i in range(1,n+1):
    counter=2
    while(w >= weights[i]*counter):
        weights.append(weights[i]*counter)
        values.append(values[i]*counter)
        counter = counter+1

dp = [[0 for i in range(w+1)]for j in range(len(values))]

for i in range(1,len(values)):
    for j in range(w+1):
        if(weights[i] > j):
            dp[i][j] = dp[i-1][j]
        else:
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-weights[i]]+values[i])

print((dp[len(values)-1][-1]))


# Optimized solution
n,w = list(map(int, input().split()))
values = []
weights = []

for i in range(n):
    v,weight = list(map(int, input().split()))
    values.append(v)
    weights.append(weight)

dp = [0 for i in range(w+1)]

for i in range(n):
    for j in range(weights[i], w+1):
        dp[j] = max(dp[j], dp[j-weights[i]]+values[i])

print((dp[w]))
# Original solution
# Knapsack Problem
N, W = [int(x) for x in input().split()]
items = []
for i in range(N):
    items.append(tuple(int(x) for x in input().split()))


DP = [[0] * (W+1) for _ in range(N+1)]
for i in range(N):
    for j in range(W+1):
        v, w = items[i]
        if w <= j:
            DP[i+1][j] = max(DP[i][j], v + DP[i+1][j-w])
        else:
            DP[i+1][j] = DP[i][j]

print((DP[-1][-1]))

# Optimized solution
# Knapsack Problem
N, W = [int(x) for x in input().split()]
items = []
for i in range(N):
    items.append(tuple(int(x) for x in input().split()))


DP = [0] * (W+1)
for i in range(N):
    v, w = items[i]
    for j in range(w, W+1):
        DP[j] = max(DP[j], v + DP[j-w])

print((DP[-1]))
# Original solution
n = int(eval(input()))
for _ in range(n):
    print((input().replace("Hoshino", "Hoshina")))

# Optimized solution
n = int(input())
dataset = [input().replace("Hoshino", "Hoshina") for _ in range(n)]
print(*dataset, sep="\n")
# Original solution
N, M = list(map(int, input().split()))
from math import sqrt

def divisor(num):
    max_num = int(sqrt(num))
    divisor_list = []
    for i in range(1, max_num + 1):
        if num % i == 0:
            divisor_list.append(i)
            divisor_list.append(num//i)
    return divisor_list

g_list = divisor(M)
g_list.sort(reverse=True)
ans = 0
for g in g_list:
    if M//g >= N:
        ans = g
        break
print(ans)

# Optimized solution
### ABC112D Partition Diff:

N, M = list(map(int, input().split()))
from math import sqrt

def divisor(num):
    max_num = int(sqrt(num))
    divisor_list = []
    for i in range(1, max_num + 1):
        if num % i == 0:
            divisor_list.append(i)
            divisor_list.append(num//i)
    return divisor_list

div = divisor(M)
div.sort(reverse=True)
ans = None
for g in div:
    if N > M//g:
        continue
    ans = g
    break
print(ans)
# Original solution
n,m=list(map(int,input().split()))
for i in range(n,m+1):
  if m%i==0:
    print((m//i))
    exit()

# Optimized solution
n,m=list(map(int,input().split()))
for i in range(2,m):
  if i*i>m:
    print((1))
    exit()
  if m%i==0:
    break
for i in range(n,m+1):
  if m%i==0:
    print((m//i))
    exit()
# Original solution
n,m=list(map(int,input().split()))
L=[]
x=m/n
for i in range(1,int(x+1)):
  if m%i==0:
    if i<=x:
      L.append(i)
    if m//i<=x:
      L.append(m//i)
print((max(L)))

# Optimized solution
n,m=list(map(int,input().split()))
L=[]
x=m/n
for i in range(1,min(int(x)+1,int(m**0.5)+1)):
  if m%i==0:
    if i<=x:
      L.append(i)
    if m//i<=x:
      L.append(m//i)
print((max(L)))
# Original solution
# 解説AC．


def main():
    N, M = list(map(int, input().split(" ")))
    result = 1
    for i in range(2, M // N + 1):
        if M % i == 0:
            result = i
    print(result)


if __name__ == '__main__':
    main()

# Optimized solution
def main():
    N, M = list(map(int, input().split(" ")))
    for i in range(M // N, 0, -1):
        if M % i == 0 and i <= M / N:
            print(i)
            break


if __name__ == '__main__':
    main()
# Original solution

lis = []

N,M = [int(i) for i in input().split()]
M_ = M
i = 2

while True:
    if M % i == 0:
        M = M // i
        lis.append(i)
    elif M == 1:
        break
    else:
        i += 1
ans = M_
ret = 1
for n in range(2**len(lis)):
    m = bin(n)[-1:1:-1]
    ret = 1
    for l in range(len(m)):
        if int(m[l]):
            ret *= lis[l]
            if  ret >= N:
                continue
    if ret >= N and ret <=ans:
        ans = ret

print((M_//ans))


# Optimized solution
import  math
lis = []

N,M = [int(i) for i in input().split()]

for i in range(1,int(math.sqrt(M))):
    if M % i == 0:
        lis.append(i)
        lis.append(M//i)


lis.sort()
i =1
for i in lis:
    if i >= N:
        break

print((M//i ))
# Original solution
import math, sys
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque
from copy import deepcopy
from functools import lru_cache
from heapq import heapify, heappop, heappush
from itertools import accumulate, combinations, permutations
input = sys.stdin.readline
mod = 10**9 + 7
ns = lambda: input().strip()
ni = lambda: int(input().strip())
nm = lambda: list(map(int, input().split()))
nl = lambda: list(map(int, input().split()))

def main():

    def make_divisors(n):
        divisors = []
        for i in range(1, int(n**0.5)+1):
            if n % i == 0:
                divisors.append(i)
                if i != n // i:
                    divisors.append(n//i)
        divisors.sort(reverse=True)
        return divisors

    n, m = nm()

    for divisor in make_divisors(m):
        if divisor <= m / n:
            print(divisor)
            exit()

if __name__ == '__main__':
    main()

# Optimized solution
import math, sys
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque
from copy import deepcopy
from functools import lru_cache
from heapq import heapify, heappop, heappush
from itertools import accumulate, combinations, permutations
input = sys.stdin.readline
mod = 10**9 + 7
ns = lambda: input().strip()
ni = lambda: int(input().strip())
nm = lambda: list(map(int, input().split()))
nl = lambda: list(map(int, input().split()))

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    divisors.sort(reverse=True)
    return divisors

n, m = nm()

for divisor in make_divisors(m):
    if divisor <= m / n:
        print(divisor)
        exit()
# Original solution
import copy
def cd_generator(num):
    ans=[]
    for i in range(1,10000000):
        if num%i==0:
            ans.append(i)
    temp=copy.deepcopy(ans)
    temp.reverse()
    for ele in temp:
        ans.append(num//ele)
    return ans
def main():
    n,m=list(map(int,input().split()))
    array=cd_generator(m)
    ans=0
    for ele in array:
        if m//ele>=n:
            ans=max(ans,ele)
    print(ans)
main()

# Optimized solution
def make_divisors(n):
    lower_divisors,upper_divisors=[],[]
    i=1
    while i*i<=n:
        if n%i==0:
            lower_divisors.append(i)
            if i!=n//i:
                upper_divisors.append(n//i)
        i+=1
    return lower_divisors+upper_divisors[::-1]
n,m=list(map(int,input().split()))
array=make_divisors(m)
array.reverse()
for ele in array:
    if m//ele>=n:
        print(ele)
        exit()
# Original solution
def make_divisors(n):
    lower_divisors,upper_divisors=[],[]
    i=1
    while i*i<=n:
        if n%i==0:
            lower_divisors.append(i)
            if i!=n//i:
                upper_divisors.append(n//i)
        i+=1
    return lower_divisors+upper_divisors[::-1]
n,m=list(map(int,input().split()))
array=make_divisors(m)
array.reverse()
for ele in array:
    if m//ele>=n:
        print(ele)
        exit()


# Optimized solution
def cd_generator(num):
    i=1
    lower=[]
    upper=[]
    while i*i<=num:
        if num%i==0:
            lower.append(i)
            if num!=i*i:
                upper.append(num//i)
        i+=1
    return reversed(lower+upper[::-1])
n,m=list(map(int,input().split()))

for ele in cd_generator(m):
    if m/ele>=n:
        print(ele)
        exit()
# Original solution
# ANSHUL GAUTAM
# IIIT-D

from math import *
from string import *
from itertools import *
from copy import *

N,M = list(map(int, input().split()))
for i in range(M//N,0,-1):
	if(M%i == 0):
		print(i)
		break

# Optimized solution
def solve():
    n, m = list(map(int, input().split()))
    for i in range(m//n,0,-1):
        if m % i == 0:
            break
    print(i)
 
solve()