Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

from collections import deque

INF = 10**12

H, W = map(int, input().split())
sx, sy = map(int, input().split())
gx, gy = map(int, input().split())
sx -= 1
sy -= 1
gx -= 1
gy -= 1
walk = [(0, 1), (0, -1), (-1, 0), (1, 0)]
warp = [(i, j) for i in range(-2, 3)
        for j in range(-2, 3) if (i, j) not in [(0, 0)] + walk]
maze = []

for _ in range(H):
    maze.append(list(input()))

q = deque()
d = [[INF] * W for i in range(H)]
d[sx][sy] = 0
q.appendleft((sx, sy, 0))

while q:
    x, y, s = q.popleft()
    for dx, dy in walk:
        nx = x + dx
        ny = y + dy
        if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] == '.' and d[nx][ny] > s:
            d[nx][ny] = s
            q.appendleft((nx, ny, s))
    for dx, dy in warp:
        nx = x + dx
        ny = y + dy
        if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] == '.' and d[nx][ny] > s+1:
            d[nx][ny] = s + 1
            q.appendleft((nx, ny, s+1))

if d[gx][gy] == INF:
    print(-1)
else:
    print(d[gx][gy])


### FIXED CODE ###

from collections import deque


H, W = map(int, input().split())
Ch, Cw = map(lambda x: int(x) - 1, input().split())
Dh, Dw = map(lambda x: int(x) - 1, input().split())
maze = [input() for _ in range(H)]

INF = 10 ** 12
path = [[INF] * W for _ in range(H)]  # path: 各マスへの移動コスト

# walk:移動A, warp:移動B
walk = [(0, 1), (0, -1), (-1, 0), (1, 0)]
warp = [(i, j) for i in range(-2, 3) for j in range(-2, 3) if (i, j) not in [(0, 0)] + walk]

q = deque()
path[Ch][Cw] = 0
q.append((Ch, Cw, 0))

while q:
    x, y, s = q.popleft()
    for dx, dy in walk:  # 移動A
        nx = x + dx
        ny = y + dy
        if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] == '.' and path[nx][ny] > s:
            path[nx][ny] = s
            q.appendleft((nx, ny, s))  # 移動Aの場合はコスト0. キューの先頭に追加する.
    for dx, dy in warp:  # 移動B
        nx = x + dx
        ny = y + dy
        if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] == '.' and path[nx][ny] > s + 1:
            path[nx][ny] = s + 1
            q.append((nx, ny, s + 1))  # 移動Bの場合はコスト1. キューの最後尾に追加する.
    
ans = path[Dh][Dw] if path[Dh][Dw] < INF else '-1'
print(ans)
### BUGGY CODE ###

L, N = (int(i) for i in input().split())
X = [int(input()) for _ in range(N)]
X.insert(0, 0)

d = {("S", 0, 0, 0, 0): 0}
for _ in range(N):
    d_ = {}
    for (root, p, l, r, f), w in d.items():
        if root[-1] == "R":
            if f == 0:
                d_[(root+"R", X[-(r+1)] - L, l, r+1, 1)] = w + (L - X[-(r+1)]) + p
            d_[(root+"L", X[l+1], l+1, r, 0)] = w + X[l+1] - p
        elif root[-1] == "L":
            if f == 0:
                d_[(root+"L", X[l+1], l+1, r, 1)] = w + X[l+1] - p
            d_[(root+"R", X[-(r+1)] - L, l, r+1, 0)] = w + (L - X[-(r+1)]) + p
        else:
            d_[(root+"L", X[l+1], l+1, r, 0)] = w + X[l+1] - p
            d_[(root+"R", X[-(r+1)] - L, l, r+1, 0)] = w + (L - X[-(r+1)]) + p

    d = d_
#     print(d)
# print(max(d.items(), key=lambda x: x[1]))
print(max(d.items(), key=lambda x: x[1])[1])


### FIXED CODE ###

import math

L, N = (int(i) for i in input().split())
X = [int(input()) for _ in range(N)]
X.insert(0, 0)

X_r = [L - i for i in reversed(X)]
X_r.insert(0, 0)
X_r.pop()

def lsum(l):
    s = 0
    for i in l:
        s += i
        yield s

X_sum = list(lsum(X))
X_r_sum = list(lsum(X_r))

def f_l(p, n):
    N_tmp = N - n
    a = N_tmp // 2
    if N_tmp == 0:
        return 0
    elif N_tmp % 2 == 0:
        return 2 * X_sum[a] + X_r_sum[a + n] + X_r_sum[a + n - 1] - 2 * X_r_sum[n] + p
    else:
        return X_sum[a+1] + X_sum[a] + 2 * X_r_sum[a + n] - 2 * X_r_sum[n] + p


def f_r(p, n):
    N_tmp = N - n
    a = N_tmp // 2
    if N_tmp == 0:
        return 0
    elif N_tmp % 2 == 0:
        return 2 * X_r_sum[a] + X_sum[a + n] + X_sum[a + n - 1] - 2 * X_sum[n] + p
    else:
        return X_r_sum[a+1] + X_r_sum[a] + 2 * X_sum[a + n] - 2 * X_sum[n] + p

max_l = max(X[i] + f_r(X[i], i) for i in range(1, N+1))
max_r = max(X_r[i] + f_l(X_r[i], i) for i in range(1, N+1))

print(max(max_l, max_r))
### BUGGY CODE ###

import math
n = int(input())
res=0
for i in range(1,n):

    cnt=0
    for j in range(1,int(math.sqrt(i))+1):
        if i%j==0:
            cnt+=2
    if math.sqrt(i)==int(math.sqrt(i)):
        cnt-=1
    res+=cnt
print(res)
    
    

### FIXED CODE ###


n = int(input())
res=0
for i in range(1,n-1):
    res+=(n-1)//i
print(res+1)
### BUGGY CODE ###

from collections import deque

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

L.sort(reverse=True)

List = deque()
Sum = 0

for i in range(1, N - 1):
    for j in range(i + 1, N):
        List.append(L[i] + L[j])

for i in range(N - 2):
    for j in range(len(List)):
        if List[j] > L[i]:
            Sum += 1

    for j in range(N-2-i):
        List.popleft()

print(Sum)

### FIXED CODE ###

import bisect

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

Sum = 0
L.sort(reverse=False)

for i in reversed(range(2,N)):
    for j in reversed(range(1,i)):
        hoge = 0
        hoge = j - bisect.bisect(L, L[i] - L[j])
        if hoge < 0:
            hoge = 0
        Sum += hoge

print(Sum)
### BUGGY CODE ###

n, w = (int(x) for x in input().split())
wv = [[0, 0]]
for _ in range(n):
    wv.append([int(x) for x in input().split()])
dp = [[0] * (w + 1) for _ in range(n + 1)]
for i in range(w + 1):
    dp[0][i] = 0
for i in range(1, n + 1):
    for j in range(1, w + 1):
        if j - wv[i][0] >= 0:
            dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - wv[i][0]] + wv[i][1])
        else:
            dp[i][j] = dp[i - 1][j]
print(dp[n][w])

### FIXED CODE ###

n, w = (int(x) for x in input().split())
wv = [[0, 0]]
for _ in range(n):
    wv.append([int(x) for x in input().split()])
dp = [[0] * (w + 1) for _ in range(n + 1)]
for i in range(w + 1):
    dp[0][i] = 0
for i in range(1, n + 1):
    for j in range(1, w + 1):
        if j - wv[i][0] >= 0:
            dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - wv[i][0]] + wv[i][1])
        else:
            dp[i][j] = dp[i - 1][j]
print(dp[n][w])
### BUGGY CODE ###

n, m = map(int, input().split())
h_list = list(map(int, input().split()))
loads = []
count = 0
for k in range(m):
    load = list(map(int, input().split()))
    loads.append(load)

for h in range(n):
    for load in loads:
        if h+1 in load:
            op = sum(load)-(h+1)-1
            if h_list[h] <= h_list[op]:
                h_count = 0
                break
    else:
        h_count = 1
        count += h_count

print(count)

### FIXED CODE ###

n, m = map(int, input().split())
h_list = list(map(int, input().split()))
loads = [[0] for i in range(n)]
count = 0
for k in range(m):
    start, end = map(int, input().split())
    loads[start-1].append(h_list[end-1])
    loads[end-1].append(h_list[start-1])

for k in range(n):
    if h_list[k] > max(loads[k]):
        count += 1

print(count)
### BUGGY CODE ###

n,m = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
bc = sorted([list(map(int, input().split())) for i in range(m)], key =lambda x:x[1])

t = True
cnt = 0

while t == True and cnt < len(bc):
  cnt += 1
  num = bc[-cnt][0]
  large = bc[-cnt][1]
  if large > min(a):
    for i in a:
      if i < large and a.index(i)+1 <= num:
        a[a.index(i)] = large
      else:
        break
    a.sort()
  else:
     t = False

print(sum(a))

### FIXED CODE ###

n,m = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
bc = sorted([list(map(int, input().split())) for i in range(m)], key =lambda x:x[1])
bc.reverse()

flg = 0
cnt = 0

for i in range(n):
  if bc[flg][1] >a[i] and flg < m:
    a[i] = bc[flg][1]
    cnt +=1
    if cnt == bc[flg][0]:
      flg += 1
      cnt = 0
      if flg == m:
        break
  else:
      break

print(sum(a))
### BUGGY CODE ###

import numpy as np
import functools
import operator

prod2 = functools.partial(functools.reduce, operator.mul)

n = int(input())
nums = list(map(int, input().split()))

val = prod2(nums)

if val > 1e18:
    val = -1

print(val)


### FIXED CODE ###

import numpy as np
import functools
import operator

prod2 = functools.partial(functools.reduce, operator.mul)

n = int(input())
nums = list(map(int, input().split()))

# val = prod2(nums)

val = 1
if 0 in nums:
    val = 0

else:
    for num in nums:
        val *= num
    
        if val > 1e18:
            val = -1
            break


print(val)
### BUGGY CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
from collections import Counter 
def main():
    N = int(readline())
    A = [int(i) for i in readline().split()]
    d = Counter(A)
    for i in A:
        ans = 0
        for key, val in d.items():
            if i == key:
                val -= 1
            ans += val*(val-1)//2 
        print(ans)
if __name__ == '__main__':
    main()


### FIXED CODE ###

#python3
from collections import Counter
def C2(x):
    return x*(x-1)//2

def main():
    n = int(input())
    a = [int(i) for i in input().split()]
    d = Counter(a) 
    pans = 0
    for v in d.values():
        pans += C2(v)

    for k in range(n):
        p = pans
        val = d[a[k]]
        p = p - C2(val) + C2(val-1)
        print(p)
main()
### BUGGY CODE ###

import copy

n,k = map(int, input().split())
a = list(map(int, input().split()))

new_a = [0 for i in range(n)]
for i in range(k):
    for j in range(n):
        for k in range(j-a[j],j+a[j]+1):
            if k < 0 or n <= k:
                continue
            else:
                new_a[k] += 1
    a = copy.copy(new_a)
    new_a = [0 for i in range(n)]

print(" ".join(list(map(str, a))))


### FIXED CODE ###

import copy
import sys
input = sys.stdin.readline

n,k = map(int, input().split())
a = list(map(int, input().split()))

new_a = [0 for i in range(n)]
for i in range(k):
    for j in range(n):
        new_a[max(j-a[j], 0)] += 1
        if j+a[j]+1 < n:
            new_a[j+a[j]+1] += -1
    for j in range(n):
        if j > 0:
            new_a[j] += new_a[j-1]
    if new_a == [n for i in range(n)]:
        a = copy.copy(new_a)
        break
    a = copy.copy(new_a)
    new_a = [0 for i in range(n)]

print(" ".join(list(map(str, a))))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10000)

n, m = map(int, input().split())
abc = [tuple(int(x) - 1 for x in input().split()) for _ in range(m)]

dist = [[9999999 for _ in range(n)] for _ in range(n)]

e = [dict() for _ in range(n)]

for i in range(m):
    a, b, c = abc[i][0], abc[i][1], abc[i][2]
    e[a][b] = c + 1
    e[b][a] = c + 1

for i in range(n):
    dist[i][i] = 0
    temp = set()
    temp.add(i)
    while len(temp) < n:
        next = -1
        nc = 99999999
        for x in temp:
            for y in e[x].keys():
                if y in temp:
                    continue
                if dist[i][x] + e[x][y] < nc:
                    nc = dist[i][x] + e[x][y]
                    next = y
        temp.add(next)
        dist[i][next] = nc

ans = m
for a, b, c in abc:
    for i in range(n):
        if c + 1 == dist[a][i] - dist[b][i]:
            ans -= 1
            break
print(ans)

### FIXED CODE ###

import heapq

n, m = map(int, input().split())
abc = [tuple(int(x) - 1 for x in input().split()) for _ in range(m)]

dist = [[9999999 for _ in range(n)] for _ in range(n)]

e = [dict() for _ in range(n)]

for i in range(m):
    a, b, c = abc[i][0], abc[i][1], abc[i][2]
    e[a][b] = c + 1
    e[b][a] = c + 1

for i in range(n):
    h = []
    heapq.heappush(h, [0, i])
    temp = set()
    #temp.add(i)
    while len(temp) < n:
        d, p = heapq.heappop(h)
        while p in temp:
            d, p = heapq.heappop(h)
        dist[i][p] = d
        temp.add(p)
        for x in e[p].keys():
            heapq.heappush(h, [d + e[p][x], x])

#for i in range(n): print(dist[i])

ans = m
for a, b, c in abc:
    for i in range(n):
        if c + 1 == dist[a][i] - dist[b][i]:
            ans -= 1
            break
print(ans)
### BUGGY CODE ###

S = int(input())
if S <= 10**9:
    print(0,0,S,0,0,1)
else:
    l = []
    for i in range(1,int(S**0.5)+1):
        if S%i == 0:
            l.append(i)
    for i in range(len(l)):
        if l[i] <= 10**9 and S//l[i] <= 10**9:
            print(0, 0, l[i], 0, 0, S//l[i])
            exit()

### FIXED CODE ###

S = int(input())
if S <= 10**9:
    print(0,0,S,0,0,1)
elif S == 10**18:
    print(0,0,10**9,0,0,10**9)
else:
    xb = int(S**0.5 + 1)
    yc = int(S**0.5 + 1)
    xc = xb*yc - S
    print(0, 0, xb, 1, xc, yc)
### BUGGY CODE ###

import queue
n,q = map(int,input().split())
branch = queue.Queue()
for _ in range(n-1):
    ab = list(map(int,input().split()))
    branch.put(ab)
count = [0]*n
for _ in range(q):
    p,x = map(int,input().split())
    count[p-1] += x
    
tree = [set() for i in range(n)]
check = [0]*n
check[0] = 1

while not branch.empty():
    a,b = branch.get()
    if check[a-1] == 0 & check[b-1] == 0:
        branch.put([a,b])
        continue
    elif check[a-1] == 1:
        tree[a-1].add(b-1)
        check[b-1] = 1
    else:
        tree[b-1].add(a-1)
        check[a-1] = 1   
    
q = queue.Queue()
q.put(0)
while not q.empty():
    num = q.get()
    for k in tree[num]:
        count[k] += count[num]
        q.put(k)
        
print(*count)

### FIXED CODE ###

n,q = map(int,input().split())
tree = [set() for _ in range(n)]
for _ in range(n-1):
    a,b = map(int,input().split())
    tree[a-1].add(b-1)
    tree[b-1].add(a-1)
count = [0]*n
for _ in range(q):
    p,x = map(int,input().split())
    count[p-1] += x
    
stack = [[0,0,-1]] # [number,count,pair]
while stack:
    num,cnt,pr = stack.pop()
    count[num] += cnt
    for k in tree[num]:
        if k == pr:
            continue
        stack.append([k,count[num],num])
        
print(*count)
### BUGGY CODE ###

from functools import lru_cache

N,W=map(int,input().split())
weights,profits = [0]*N, [0]*N

@lru_cache(None)
def knapsack_recursive(capacity, currentIndex):
 
  # base checks
    if capacity <= 0 or currentIndex >= len(profits): return 0

    profit1 = 0
    if weights[currentIndex] <= capacity:
        profit1 = profits[currentIndex] + knapsack_recursive(capacity - weights[currentIndex], currentIndex + 1)
    profit2 = knapsack_recursive(capacity, currentIndex + 1)
    return max(profit1, profit2)
  
def main():

    for i in range(N):
        weights[i],profits[i] = map(int,input().split())
    res = knapsack_recursive(W, 0)
 
    print(res)
if __name__ == "__main__":
	main()

### FIXED CODE ###

def main():
  n, w = [int(e) for e in input().split()]
  t = [-1 for i in range(w + 1)]
  t[w] = 0
  for _ in range(n):
    nw, nv = [int(e) for e in input().split()]
    for i in range(nw, w + 1):
      if t[i] == -1:
        continue
      if t[i - nw] < t[i] + nv:
        t[i - nw] = t[i] + nv
  print(max(t))
main()
### BUGGY CODE ###

def MAIN():
    H, W = map(int, input().split())
    MAP = tuple(input() for _ in range(H))
    R, C = map(int, input().split())
    PTN = tuple(input() for _ in range(R))
    def solve(a, b):
        k = 0
        for i in range(a, a + R):
            if MAP[i][b:b + C] == PTN[k]:
                k += 1
            else:
                return False
        return True
    ans = []
    for i in range(H - R + 1):
        if PTN[0] not in MAP[i]:
            continue
        j = MAP[i].find(PTN[0])
        while j != -1:
            if solve(i, j):
                ans.append(f"{i} {j}")
            j = MAP[i].find(PTN[0], j + 1)
    if ans:
        print("\n".join(a for a in ans))
MAIN()



### FIXED CODE ###

base1 = 1009
base2 = 1013
mask = (1 << 32) - 1
def calc_hash(f, r, c):
    global ph, pw, h
    tmp = [[0] * c for _ in range(r)]
    dr, dc = r - ph, c - pw
    # t1 = 1
    t1 = (base1 ** pw) & mask
    # for _ in range(pw):
        # t1 = (t1 * base1) & mask
    for i in range(r):
        e = 0
        for j in range(pw):
            e = e * base1 + f[i][j]
        for j in range(dc):
            tmp[i][j] = e
            e = (e * base1 - t1 * f[i][j] + f[i][j + pw]) & mask
        tmp[i][dc] = e
    t2 = 1
    for _ in range(ph):
        t2 = (t2 * base2) & mask
    for j in range(dc + 1):
        e = 0
        for i in range(ph):
            e = e * base2 + tmp[i][j]
        for i in range(dr):
            h[i][j] = e
            e = (e * base2 - t2 * tmp[i][j] + tmp[i + ph][j]) & mask
        h[dr][j] = e
th, tw = map(int, input().split())
t = tuple(tuple(ord(c) for c in input()) for _ in range(th))
ph, pw = map(int, input().split())
p = tuple(tuple(ord(c) for c in input()) for _ in range(ph))
ans = []
if th >= ph and tw >= pw:
    h = [[0] * tw for _ in range(th)]
    calc_hash(p, ph, pw)
    key = h[0][0] & mask
    calc_hash(t, th, tw)
    for i in range(th - ph + 1):
        for j in range(tw - pw + 1):
            if h[i][j] & mask == key:
                ans.append(f"{i} {j}")
if ans:
    print("\n".join(a for a in ans))
### BUGGY CODE ###

l, r = map(int, input().split())

ans = 1000000000
for i in range(l, r):
  for j in range(i + 1, r + 1):
    ans = min((i * j) % 2019, ans)
    #割り切れた場合はそれが最小値なので探索終了とする
    if ans == 0:
      break

print(ans)

### FIXED CODE ###

l, r = map(int, input().split())
r = min(r, l + 4038)
ans = 2018
for i in range(l, r):
  for j in range(i + 1, r + 1):
    ans = min((i * j) % 2019, ans)
    #割り切れた場合はそれが最小値なので探索終了とする
    if ans == 0:
      break

print(ans)
### BUGGY CODE ###

MOD = 10**9+7
N = int(input())
A = list(map(int, input().split()))
 
ans = 0
twopow = 1
for n in range(60):
    one = 0
    for i in range(N):
        one += A[i] & 1
        A[i] >>= 1
    zero = N - one
    ans = (ans + (one * zero) * twopow) % MOD
    twopow = twopow << 1 % MOD

print(ans)

### FIXED CODE ###

import numpy as np
MOD = 10**9+7
N = int(input())
A = list(map(int, input().split()))
A = np.array(A)

ans = 0
twopow = 1
for n in range(60):
    tmp = A & 1
    one = np.count_nonzero(tmp)
    zero = N - one
    ans = (ans + (one * zero) * twopow) % MOD
    A >>= 1
    twopow = twopow << 1 % MOD

print(ans)
### BUGGY CODE ###

# -*- coding: utf-8 -*-

import sys
from collections import deque

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N = INT()
A = [deque()]
for i in range(N):
    A.append(deque(LIST()))

cnt = N*(N-1)//2
day = 0
while cnt > 0:
    prev = cnt
    skip = [False] * (N+1)
    for i in range(1, N+1):
        if len(A[i]) and not skip[i]:
            a = A[i][0]
            if len(A[a]) and not skip[a]:
                b = A[a][0]
                if i == b:
                    A[i].popleft()
                    A[a].popleft()
                    cnt -= 1
                    skip[i] = skip[a] = True
    if prev == cnt:
        print(-1)
        exit()
    day += 1
    if day > 500000:
        print(N*(N-1)//2)
        exit()
print(day)


### FIXED CODE ###

# -*- coding: utf-8 -*-

import sys
import time
from collections import deque

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N = INT()
A = [deque()]
for i in range(N):
    A.append(deque(LIST()))

start = time.time()

cnt = N*(N-1)//2
day = 0
while cnt > 0:
    prev = cnt
    skip = [False] * (N+1)
    for i in range(1, N+1):
        if len(A[i]) and not skip[i]:
            a = A[i][0]
            if len(A[a]) and not skip[a]:
                b = A[a][0]
                if i == b:
                    A[i].popleft()
                    A[a].popleft()
                    cnt -= 1
                    skip[i] = skip[a] = True
    if prev == cnt:
        print(-1)
        exit()
    day += 1

    elapsed_time = time.time() - start
    if elapsed_time > 1:
        print(N*(N-1)//2)
        exit()
print(day)
### BUGGY CODE ###

S = input()
k = int(input())
A = []

for i in range(len(S) + 1):
    for j in range(i + 1, len(S) + 1):
        A.append(S[i:j])
        
ans = sorted(list(set(A)))
print(ans[k - 1])

### FIXED CODE ###

S = input()
k = int(input())
A = []

for i in range(len(S)):
    for j in range(1, k + 1):
        A.append(S[i : i + j])
        
ans = sorted(list(set(A)))
print(ans[k - 1])
### BUGGY CODE ###

n,m=map(int,input().split())
ans=0
k=0
i=m//n
while k==0:
    if m%i==0:
        ans=i
        k=1
    i-=1
    
print(ans)

### FIXED CODE ###

n,m=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()
    divisors.reverse()
    return divisors

l=make_divisors(m)

for i in l:
    if i*n<=m:
        print(i)
        import sys
        sys.exit()
### BUGGY CODE ###

t=int(input())
l=[list(map(int,input().split())) for i in range(t)]
for i in range(t):
  ans=[]
  for j1 in range(70):
    for j2 in range(70):
      for j3 in range(70):
        x=(2**j1)*(3**j2)*(5**j3)
        ans.append(l[i][1]*j1+l[i][2]*j2+l[i][3]*j3+l[i][4]+l[i][4]*(abs(x-l[i][0])))
  print(min(ans))

### FIXED CODE ###

import math
import sys
from functools import lru_cache
sys.setrecursionlimit(10**6)
t=int(input())
for i in range(t):
  n,a,b,c,d=map(int,input().split())
  @lru_cache(maxsize=None)
  def f(n):
    if n==0:
      return 0
    if n==1:
      return d
    else:
      x=n*d
      
      q,r=divmod(n,2)
      if r==0:
        x=min(x,f(q)+a)
      else:
        x=min(x,f(q)+a+d,f(q+1)+a+d)
      
      q,r=divmod(n,3)
      if r==0:
        x=min(x,f(q)+b)
      elif r==1:
        x=min(x,f(q)+b+d,f(q+1)+b+d*2)
      else:
        x=min(x,f(q)+b+d*2,f(q+1)+b+d)
      
      q,r=divmod(n,5)
      if r==0:
        x=min(x,f(q)+c)
      elif r==1:
        x=min(x,f(q)+c+d,f(q+1)+c+d*4)
      elif r==2:
        x=min(x,f(q)+c+d*2,f(q+1)+c+d*3)
      elif r==3:
        x=min(x,f(q)+c+d*3,f(q+1)+c+d*2)
      else:
        x=min(x,f(q)+c+d*4,f(q+1)+c+d)
      
      return x
  
  print(f(n))
### BUGGY CODE ###

import fractions
import math

AB = list(map(int, input().split()))
A = AB[0]
B = AB[1]

GCM = fractions.gcd(A, B)

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()
    return divisors

def isPrime(n):
    if n < 2:
        return False
    if n == 2:
        return True
    for p in range(2,n):
        if n % p == 0:
            return False
    return True

divisors = make_divisors(GCM)

cnt = 0
for divisor in divisors:
    if isPrime(divisor):
        cnt += 1
    if divisor > int(divisors[-1]/2):
        break

print(cnt+1)


### FIXED CODE ###

import fractions
import collections
import math

AB = list(map(int, input().split()))
A = AB[0]
B = AB[1]

GCM = fractions.gcd(A, B)

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()
    return divisors

def isPrime(n):
    if n < 2:
        return False
    if n == 2:
        return True
    for p in range(2,n):
        if n % p == 0:
            return False
    return True

def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

c = collections.Counter(prime_factorize(GCM))
print(len(list(c.keys()))+1)