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

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

N = int(input())
p_list = []
count = 0

while N > 0:
    S = input()
    if S not in p_list:
        p_list.append(S)
        count += 1
    else:
        pass
    N -= 1

print(count)

### FIXED CODE ###

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

N = int(input())
p_list = []

while N > 0:
    S = input()
    p_list.append(S)
    N -= 1

p_set = (set(p_list))
print(len(p_set))
### BUGGY CODE ###

from collections import defaultdict
N = int(input())
XYH = [list(map(int,input().split())) for _ in range(N)]

Cxy = defaultdict(int)

#-1 NG
# 0 default
#1+ ok
verify =[]
for x,y,h in XYH:
    for cx in range(101):
        for cy in range(101):
            val = Cxy[(cx,cy)]
            if val<0:
                continue
            tmp_H = abs(x-cx)+abs(y-cy)+h
            if h==0:
                verify.append((x,y,h))
                continue #????

            if val==0:
                Cxy[(cx,cy)] = tmp_H
            elif val != tmp_H:
                Cxy[(cx, cy)] =-1

def find(d):
    for key in d.keys():
        if d[key] >0:

            if any((d[key]-abs(key[0]-x) - abs(key[1]-y))>0  for x,y,h in verify):
                continue

            return key,d[key]

(X,Y),H = find(Cxy)
print(X,Y,H)

### FIXED CODE ###

from collections import defaultdict
N = int(input())
XYH = [list(map(int,input().split())) for _ in range(N)]

Cxy = defaultdict(int)

#-1 NG
# 0 default
#1+ ok
verify =[]
XYH.sort(key=lambda x:-x[2])

for x,y,h in XYH:
    for cx in range(101):
        for cy in range(101):
            val = Cxy[(cx,cy)]
            if val<0:
                continue
            tmp_H = abs(x-cx)+abs(y-cy)+h
            if h==0:
                if tmp_H < Cxy[(cx,cy)]:
                    Cxy[((cx, cy))]=-1
                continue

            if val==0:
                Cxy[(cx,cy)] = tmp_H
            elif val != tmp_H:
                Cxy[(cx, cy)] =-1

def find(d):
    for key in d.keys():
        if d[key] >0:

            return key,d[key]

(X,Y),H = find(Cxy)
print(X,Y,H)
### BUGGY CODE ###

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

plist = list(map(int,input().split()))

maxval = 0

temp = -1

def expectedval(inp):
	return (1 + inp) /2

for i in range(n-(k-1)):
	summ = 0
	if temp == -1:
		for j in range (k):
			summ += expectedval(plist[i + j])
	else:
		summ = summ - expectedval(plist(i - 1)) + expectedval(plist(i + k))
	maxval = max(summ, maxval)

print(maxval)

### FIXED CODE ###

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

plist = list(map(int,input().split()))

maxval = 0

temp = -1

def expectedval(inp):
	return (1 + inp) /2

for i in range(n-(k-1)):
	# print(i, k)
	summ = 0
	if temp == -1:
		for j in range (k):
			summ += expectedval(plist[i + j])
		temp = summ
	else:
		# print(plist[i-1], plist[i+k -1], expectedval(plist[i - 1]), expectedval(plist[i + k - 1]))
		summ = temp - expectedval(plist[i - 1]) + expectedval(plist[i + k - 1])
		temp = summ
	# print(summ)
	maxval = max(summ, maxval)

print(maxval)
### BUGGY CODE ###

def isok(z,val):##適宜変更
    if z-val<=2*d:
        return True
    else:
        return False
def bisect(ls,val): ##valの関数isok(x,val)がTrueとなる一番右のindex を返す 全部Falseなら-1
    ok = -1
    ng = len(ls)
    idx = (ok+ng)//2
    while ng-ok>1:
        num = ls[idx]
        if isok(num,val):
            ok = idx
        else:
            ng = idx
        idx = (ok+ng)//2
    return ok ##一番右のTrueのindex  Trueの個数はok+1こ


import sys
import math
input = sys.stdin.readline
ceil = math.ceil
n,d,a = map(int,input().split())
mon = []
for i in range(n):
    x,h = map(int,input().split())
    mon.append((x,h))
mon.sort()
keys = [ls[0] for ls in mon] #bisect用の配列



damage = [0]*(2*n+1)
ans = 0
for i in range(n):
    x,h = mon[i]
    res = h-damage[i]
    if res>0:##体力が残ってたら
        c = ceil(res/a)
        ans+=c
        idx = bisect(keys[i:],x) ##爆風が届くぎりぎりの位置
        if idx==-1:continue
        damage[i] +=a*c
        damage[i+idx+1] -=a*c
    damage[i+1] += damage[i]
print(ans)


### FIXED CODE ###

import sys
import math
input = sys.stdin.readline
ceil = math.ceil

def main():
    def isok(z,val):##適宜変更
        return (z-val<=2*d)
    def bisect(ls,val): ##valの関数isok(x,val)がTrueとなる一番右のindex を返す 全部Falseなら-1
        ok = -1
        ng = len(ls)
        idx = (ok+ng)//2
        while ng-ok>1:
            num = ls[idx]
            if isok(num,val):
                ok = idx
            else:
                ng = idx
            idx = (ok+ng)//2
        return ok ##一番右のTrueのindex  Trueの個数はok+1こ

    n,d,a = map(int,input().split())
    mon = []
    for i in range(n):
        x,h = map(int,input().split())
        mon.append((x,h))
    mon.sort()
    keys = [ls[0] for ls in mon] #bisect用の配列

    damage = [0]*(n+1)
    ans = 0
    for i in range(n):
        x,h = mon[i]
        res = h-damage[i]
        if res>0:##体力が残ってたら
            c = ceil(res/a)
            ans+=c
            idx = bisect(keys,x) ##爆風が届くぎりぎりの位置
            if idx==-1:continue
            damage[i] +=a*c
            damage[idx+1] -=a*c
        damage[i+1] += damage[i]
    print(ans)
if __name__=="__main__":
    main()
### BUGGY CODE ###

import re
N = int(input())
S = input()

ans = 0
r,g,b = 0,0,0
for i in range(N):
  if(S[i] == 'R'): r += 1
  elif(S[i] == 'G'): g += 1  
  elif(S[i] == 'B'): b += 1 
  
  # i     j    j+(j-i) : R  G  B  (or)  R  B  G (or) ... である場合 ans -= 1   
  for j in range(i+1,N-1):
     i1,i2,i3 = i,j,j+(j-i)
     if(i3 <= N-1):
       tmp = [S[i1],S[i2],S[i3]]
       tmp.sort()
       tmp = tmp[0]+tmp[1]+tmp[2]
       if(tmp == 'BGR'):
         ans -= 1

ans += r*g*b
print(ans)

### FIXED CODE ###

N = int(input())
S = input()

ans = 0
r,g,b = 0,0,0
for i in range(N):
  if(S[i] == 'R'): r += 1
  elif(S[i] == 'G'): g += 1  
  elif(S[i] == 'B'): b += 1 
  
  # i     j    j+(j-i) : R  G  B  (or)  R  B  G (or) ... である場合 ans -= 1   
  for j in range(i+1,N-1):
     i1,i2,i3 = i,j,j+(j-i)
     if(i3 <= N-1):
       tmp = [S[i1],S[i2],S[i3]]
       tmp.sort()
       tmp = tmp[0]+tmp[1]+tmp[2]
       if(tmp == 'BGR'):
         ans -= 1

ans += r*g*b
print(ans)
### BUGGY CODE ###

n, k, q = map(int, input().split())
anss = []
for i in range(q):
  anss.append(int(input()))
#N人、持ち点K、問題Q

for i in range(n):
  tmp = anss.count(i+1)
  if tmp > q-k:
    print("Yes")
  else:
    print("No")


### FIXED CODE ###

n, k, q = map(int, input().split())
#N人、持ち点K、問題Q
anss = [0] * n
tmp = 0
for i in range(q):
  tmp = int(input())
  anss[tmp-1] += 1
for i in anss:
  if i > q - k:
    print("Yes")
  else:
    print("No")
### BUGGY CODE ###

import numpy as np

N, Q = map(int, input().split())
S = input()
ls, rs = [], []
for _ in range(Q):
    l, r = map(int, input().split())
    ls.append(l-1)
    rs.append(r-1)

arr = np.zeros(N, np.int)

for i, (a, c) in enumerate(zip(S, S[1:])):
    if a == 'A' and c == 'C':
        arr[i] = 1

for l, r in zip(ls, rs):
    print(np.sum(arr[l:r]))


### FIXED CODE ###

import numpy as np

N, Q = map(int, input().split())
S = input()
ls, rs = [], []
for _ in range(Q):
    l, r = input().split()
    ls.append(int(l)-1)
    rs.append(int(r)-1)

arr = np.zeros(N, np.int)
# flag = False
# for i in range(N):
#     if S[i] == 'A':
#         flag = True
#     elif S[i] == 'C' and flag:
#         arr[i - 1] = 1
#     else:
#         flag = False
for i, (a, c) in enumerate(zip(S, S[1:])):
    if a == 'A' and c == 'C':
        arr[i] = 1

cum = np.cumsum(arr)

for l, r in zip(ls, rs):
    if l == 0:
        print(cum[r-1])
    else:
        print(cum[r-1] - cum[l-1])
### BUGGY CODE ###

N = int(input())

A = map(int, input().split())

ones = [0] * 60
m = 10 ** 9 + 7

for Ai in A:
    for digit in range(len(bin(Ai)) - 2):
        ones[digit] += ((Ai >> digit) & 1)

res = 0
for i, num in enumerate(ones):
    res = (res + (1 << i) * num * (N - num)) % m

print(res)


### FIXED CODE ###

N = int(input())

A = map(int, input().split())

num = [[0, 0] for _ in range(60)]

for Ai in A:
    for digit in range(60):
        if (Ai >> digit) & 1:
            num[digit][1] += 1
        else:
            num[digit][0] += 1

res = 0
for i, p in enumerate(num):
    res += (1 << i) * p[0] * p[1]

m = 10 ** 9 + 7
print(res % m)
### BUGGY CODE ###

### B
N, K = map(int, input().split())
A = list(map(int, input().split()))
result = 0
for i in range(N-K+1):
	K_sum = max(0, sum(A[i:i+K]))
	N_sum = K_sum + sum(map(lambda x:max(0, x), A[:i]+A[i+K:]))
	result = max(result, N_sum)
print(result)

### FIXED CODE ###

N, K = map(int, input().split())
A = list(map(int, input().split()))
k = 0
for i in range(N-K+1):
	if i>0:
		K_sum = K_sum-A[i-1]+A[i+K-1]
		K_sum0 = max(0, K_sum)
		K_pos = K_pos-max(0, A[i-1])+max(0, A[i+K-1])
	else:
		K_sum = sum(A[i:i+K])
		K_sum0 = max(0, K_sum)
		K_pos = sum(map(lambda x:max(0, x), A[i:i+K]))
	loss = K_pos-K_sum0
	if i==0:
		loss_min = loss
	if loss<loss_min:
		k = i
		loss_min = loss
K_sum_result = max(0, sum(A[k:k+K]))
result = K_sum_result + sum(map(lambda x:max(0, x), A[:k]+A[k+K:]))
print(result)
### BUGGY CODE ###

n, q = map(int, input().split())
s = input()
t = [[0 for i in range(2)] for j in range(q)]
for k in range(q):
    t[k][0], t[k][1] = map(int, input().split())

for l in range(q):
    count = 0
    for m in range(t[l][1] - t[l][0]):
        if s[t[l][0] - 1 + m] == "A" and s[t[l][0] + m] == "C":
            count += 1

    print(count)
            


### FIXED CODE ###

n, q = map(int, input().split())
s = input()

t = [0 for i in range(len(s))]
count = 0
for j in range(len(s)-1):
    if s[j] == "A" and s[j+1] == "C":
        count += 1
    t[j+1] = count

for k in range(q):
    l, r = map(int, input().split())
    print(t[r-1] - t[l-1])
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import random
import sys

sys.setrecursionlimit(100000)
input = sys.stdin.readline

INF = 2**63-1

def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def warshall_floyd(g):
    N = len(g)
    for k in range(N):
        for i in range(N):
            for j in range(N):
                g[i][j] = min(g[i][j], g[i][k] + g[k][j])
    return g


def slv(N, M, L, ABC, Q, ST):
    g = [[INF]*(N) for _ in range(N)]

    for a, b, c in ABC:
        if c > L:
            continue
        g[a-1][b-1] = c
        g[b-1][a-1] = c

    d = warshall_floyd(g)

    gg = [[INF]*(N) for _ in range(N)]
    for u in range(N):
        for v in range(N):
            if d[u][v] <= L:
                gg[u][v] = 1

    d = warshall_floyd(gg)

    for s, t in ST:
        c = d[s-1][t-1]
        if c != INF:
            print(c-1)
        else:
            print(-1)


def main():
    N, M, L = read_int_n()
    ABC = [read_int_n() for _ in range(M)]
    Q = read_int()
    ST = [read_int_n() for _ in range(Q)]

    (slv(N, M, L, ABC, Q, ST))


if __name__ == '__main__':
    main()


### FIXED CODE ###

def slove():
    import sys
    input = sys.stdin.readline
    n, m, l = list(map(int, input().rstrip('\n').split()))
    INF = 10 ** 11
    w = [[INF] * n for _ in range(n)]
    wl = [[INF] * n for _ in range(n)]

    for i in range(n):
        w[i][i] = 0

    for i in range(m):
        a, b, c = list(map(int, input().rstrip('\n').split()))
        if c <= l:
            w[a - 1][b - 1] = c
            w[b - 1][a - 1] = c

    for i in range(n):
        for j in range(n):
            for k in range(n):
                w[j][k] = min(w[j][k], w[j][i] + w[i][k])

    for i in range(n):
        for j in range(n):
            if w[i][j] <= l:
                wl[i][j] = 1
    for i in range(n):
        for j in range(n):
            for k in range(n):
                wl[j][k] = min(wl[j][k], wl[j][i] + wl[i][k])

    q = int(input().rstrip('\n'))
    for i in range(q):
        s, t = list(map(int, input().rstrip('\n').split()))
        if wl[s-1][t-1] == INF:
            print(-1)
        else:
            print(wl[s-1][t-1] - 1)


if __name__ == '__main__':
    slove()
### BUGGY CODE ###

def findlcs(x, y):
    dp = [[0]*(len(y)+1) for i in range(len(x)+1)]

    for i in range(1, len(x)+1):
        for j in range(1, len(y)+1):
            if x[i-1] == y[j-1]:
                dp[i][j] = dp[i-1][j-1]+1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])

    return dp[len(x)][len(y)]


q = int(input())
for k in range(q):
    X = input()
    Y = input()
    print(findlcs(X, Y))

### FIXED CODE ###

def findlcs(x, y):
    dp = [0]*(len(y)+1)

    for c in x:
        tmp = dp[:]
        for j in range(len(y)):
            if c == y[j]:
                dp[j+1] = tmp[j] + 1
            elif dp[j+1] < dp[j]:
                dp[j+1] = dp[j]

    return dp[-1]


q = int(input())
for k in range(q):
    X = input()
    Y = input()
    print(findlcs(X, Y))
### BUGGY CODE ###

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

from itertools import combinations

ans = []

for i in range(1,k+1):
    print(len(list(combinations(range(n-k+1),i)))*len(list(combinations(range(k-1),i-1)))%(10**9+7))


### FIXED CODE ###

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

from math import factorial
# math.factorial(n) nの階乗

def combination(n, k):
    return factorial(n) // factorial(k) // factorial(n - k)

for i in range(1, k+1):
    if i <= n-k+1:
        print(combination(n-k+1, i)*combination(k-1,i-1)%(10**9+7))
    else:
        print(0)
### BUGGY CODE ###

import numpy as np
N,M = list(map(int,input().split()))
A = input().split()
 
count = 0
A = np.array(A,dtype='int64')
B = np.cumsum(A)
C = np.append([0],B)
 
L = (1 for i in range(len(C)) for t in range(len(C)) if i<t and (C[t] - C[i])%M==0)
print(len(list(L)))

### FIXED CODE ###

import collections
import numpy as np

N,M = list(map(int,input().split()))
A = input().split()

A = np.array(A,dtype='int64')
C = np.append([0],np.cumsum(A))
L = [i%M for i in C]
L_c = collections.Counter(L)

ans = 0
for i in L_c.values():
    S = i * (i-1) / 2
    ans+=S
    
print(int(ans))
### BUGGY CODE ###

x,y = map(int,input().split())

if x == y:
     print('-1')
else:
     i = 2 
     while True:
          if x*i == y:
               i += 1     
               pass
          elif x*i % y == 0:
               i += 1     
               pass
          else:
               print(x*i)
               break 

### FIXED CODE ###

x,y = map(int,input().split())


if x%y == 0:
     print('-1')
else:
     i = 2 
     while True:
          if x*i % y == 0:
               i += 1     
               continue
          else:
               print(x*i)
               break
### BUGGY CODE ###

n,k=map(int,input().split())
p=[]
for i in range(n):
  a,b=map(int,input().split())
  p+=[a]*b
p.sort() 




print(p[k-1])

### FIXED CODE ###

N,K = map(int,input().split())
a = []
M = 0
for i in range(N):
  a.append(list(map(int,input().split())))
a.sort()
for i in range(N):
    K = K-a[i][1]
    if K <= 0:
        print(a[i][0])
        break
### BUGGY CODE ###

n, m = map(int, input().split())
query = []
for i in range(m):
    qList = list(map(int, input().split()))
    query.append(qList)
result = [[] for i in range(n)]

for city in query:
    result[city[0]-1].append(city[1])

for i in result:
    i.sort()

for city in query:
    rank = result[city[0]-1].index(city[1])+1
    resultStr = "{}{}".format("0"*(6-len(str(city[0]))) + str(city[0]), "0"*(6-len(str(rank))) + str(rank))
    print(resultStr)

### FIXED CODE ###

def main():
    from sys import stdin
    from bisect import bisect_left

    readline = stdin.readline
    n, m = map(int, readline().split())
    data = [list(map(int, readline().split())) for _ in range(m)]
    t = [[] for _ in range(n)]

    for p, y in data:
        t[p - 1].append(y)

    for i in range(n):
        t[i].sort()

    for p, y in data:
        nth = bisect_left(t[p - 1], y) + 1
        print("%06d%06d" % (p, nth))

main()
### BUGGY CODE ###

from functools import lru_cache

N,K=[int(i) for i in input().split(" ")]
V=[int(i) for i in input().split(" ")]


def value(V,k,hands):
    if k==0:
        return sum(hands)
    else:
        retval=sum(hands)
        try:
            retval=max(value(V[1::],k-1,sorted(hands+[V[0]])),retval)
        except:
            pass
        try:
            p2=value(V[:-1:],k-1,sorted(hands+[V[-1]]))
            retval=max(retval,p2)
        except:
            pass
        try:
            p3=value(V+[hands[0]],k-1,hands[1::])
            retval=max(p3,retval)
        except:
            pass
        try:
            p4=value([hands[0]]+V,k-1,hands[1::])
            retval=max(p4,retval)
        except:
            pass
        return retval

print(value(V,K,[]))


### FIXED CODE ###

from functools import lru_cache
import numpy as np

N,K=[int(i) for i in input().split(" ")]
V=[int(i) for i in input().split(" ")]

retval=0
for left in range(max(N+1,K+1)):
    for right in range(min(N-left+1,K-left+1)):
        modoseru=K-(left+right)
        temoto=np.asarray(sorted(V[:left:]+V[N-right::]))
        modosu=min(np.sum(temoto<0),modoseru)
        retval=max(sum(temoto[modosu::]),retval)

print(retval)
### BUGGY CODE ###

def Triangles(N, L):
    asc = sorted(L)
    desc = sorted(L, reverse=True)
    cnt = 0
    for i in range(N-2):
        if desc[i] >= desc[i+1]*2: break
        for j in range(i+1, N-1):
            nokori = desc[i] - desc[j]
            tmp = [asc[i] for i in range(N-j-1) if asc[i] > nokori]
            cnt += len(tmp)
    return cnt

N = int(input())
L = [int(x) for x in input().split()]
print(Triangles(N, L))

### FIXED CODE ###

from bisect import bisect_left

def Triangles(N, L):
    asc = sorted(L)
    cnt = 0
    for i in range(N-2):
        l1 = asc[i]
        for j in range(i+1, N-1):
            l2 = asc[j]
            pos = bisect_left(asc, l1+l2)
            cnt += pos - 1 - j
    return cnt

N = int(input())
L = list(map(int, input().split()))
print(Triangles(N, L))
### BUGGY CODE ###

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

ans = 0
for i in range(N-1):
    tmp = 0
    for j in range(i, N-1):
        if H[j] >= H[j+1]:
            tmp += 1
        else: 
            break    
    ans = max(ans, tmp)
print(ans)

### FIXED CODE ###

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

ans = 0
cnt = 0

for i in range(N-1):
    if H[i] >= H[i+1]:
        cnt += 1
    else:
        if ans < cnt:
            ans = cnt
        cnt = 0    
if ans < cnt:
    ans = cnt
print(ans)
### BUGGY CODE ###

def knapsack_DP(N, W, weight, value):
    dp = [0 for _ in range(W + 1)] 
    ans=0
    for i in range(N):
        ans=max(ans, max(dp)+value[i])
        dp_tmp = [] 
        for w in range(W + 1):
            if (w >= weight[i]): 
                dp_next = max(dp[w-weight[i]] + value[i], dp[w]) 
            else:
                dp_next = dp[w] 
            dp_tmp.append(dp_next)
        dp = dp_tmp 
    return ans

if __name__=="__main__":
    N, W = map(int, input().split())
    weight = []
    value = []
    for i in range(N):
        w, v= map(int, input().split())
        weight.append(w)
        value.append(v)
    wv=((weight[i],value[i]) for i in range(N))
    wv=sorted(wv, key=lambda x:x[0])
    weight=[wv[i][0] for i in range(N)]
    value=[wv[i][1] for i in range(N)]
    print(knapsack_DP(N, W-1, weight, value))

### FIXED CODE ###

def knapsack_DP(N, W, weight, value):
    import numpy as np
    dishes = [(weight[i], value[i]) for i in range(N)]
    dishes = sorted(dishes, key=lambda x: x[0])
    dp = np.zeros(W, dtype=int)
    ans=0
    for w, v in dishes:
        ans=max(dp[-1]+v, ans)
        np.maximum(dp[:-w] + v, dp[w:], out=dp[w:]) 
    return ans

if __name__=="__main__":
    N, W = map(int, input().split())
    weight = []
    value = []
    for i in range(N):
        w, v= map(int, input().split())
        weight.append(w)
        value.append(v)
    print(knapsack_DP(N, W, weight, value))
### BUGGY CODE ###

import math
from functools import reduce
K = int(input())
ans = 0

def gcd(*numbers):
  return reduce(math.gcd, numbers)

for i in range(1, K+1):
  for j in range(1, K+1):
    for k in range(1, K+1):
      ans += gcd(i, j, k)
      
print(ans)  

### FIXED CODE ###

from math import gcd

K = int(input())
ans = 0

for i in range(1, K+1):
  for j in range(1, K+1):
    for k in range(1, K+1):
      ans += gcd(gcd(i, j), k)
      
print(ans)
### BUGGY CODE ###

S=input()
n=len(S)
K=n
while(True):
    a=n-K
    b=K
    flag=1
    for i in range(a,b-1):
        if S[i]!=S[i+1]:
            flag=0
            break
    if flag==1:
        break
    else:
        K-=1
print(K)


### FIXED CODE ###

S = input()
n = len(S)
j = 0
for i in range(1, n):
    if S[i - 1] != S[i]:
        if abs(n - 2 * i) < abs(n - 2 * j):
            j = i
print(max([j, n - j]))
### BUGGY CODE ###

import sys
input  = sys.stdin.readline

N,W=map(int,input().split())
box=[0]*(W+1)

for i in range(N):
  w,v=map(int,input().split())
  for j in range(W,0,-1):
    idx = j-w
    if idx<0:
      break
    else:
      box[j] = max(box[j],box[idx]+v)
print(box[-1])


### FIXED CODE ###

import sys
input  = sys.stdin.readline

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

def process(N,W):
  box=[0]*(W+1)
  for i in range(N):
    w,v=map(int,input().split())
    for j in range(W,0,-1):
      idx = j-w
      if idx<0:
        break
      else:
        box[j] = max(box[j],box[idx]+v)
  return box[-1]

print(process(N,W))
### BUGGY CODE ###

n,m=map(int,input().split())
import math
sosuu=[]
m0=m
i=2
while i**2<=m:
    if m0%i==0:
        sosuu.append(0)
    while m0%i==0:  
        m0=m0//i
        sosuu[-1]=sosuu[-1]+1
    i=i+1
if m0>1:
    sosuu.append(1)
def c(n,r):
    return math.factorial(n)//(math.factorial(r)*math.factorial(n-r))
answer=1
for i in sosuu:
    a=c(i+n-1,i)
    answer=(answer*a)%(10**9+7)
print(answer)



### FIXED CODE ###

n,M=map(int,input().split())
from math import factorial
i=2
c_list=[]
m=M
while not m==1:
    count=0
    while m%i==0:
        m=m//i
        count=count+1
    if not count==0:
        c_list.append(count)
    i=i+1
if M==1:
    print(1)
else:
    INF=10**9+7
    Sum=1
    for i in c_list:
        Sum=Sum*(factorial(n-1+i)//(factorial(n-1)*factorial(i)))
        Sum=Sum%INF
    print(Sum)
### BUGGY CODE ###

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

ans = a[0]
for v in a[1:]:
    ans *= v
if ans > 10**18:
    print(-1)
else:
    print(ans)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
a.sort()
ans = 1
for v in a:
    ans *= v
    if ans > 10**18:
        print(-1)
        exit()
print(ans)
### BUGGY CODE ###

R, G, B, N = map(int, input().split())
ans = 0
for r in range((N//R)+1):
    for g in range((N//G)+1):
        if r*R + g*G <= N and (N - r*R - g*G) % B == 0:
            ans += 1
print(ans)

### FIXED CODE ###

R, G, B, N = map(int, input().split())
ans = 0
for r in range((N//R)+1):
    for g in range((N//G)+1):
        if r*R + g*G <= N and (N - r*R - g*G) % B == 0:
            ans += 1
print(ans)
### BUGGY CODE ###

import sys

N, M = sys.stdin.readline().strip().split()
N = int(N)
M = int(M)
L = M//N

for x in range(L, 0, -1):
  if M % x == 0:
    print(x)
    break

### FIXED CODE ###

import sys
import math

N, M = sys.stdin.readline().strip().split()
N = int(N)
M = int(M)
P = M//N # これ以下で最大の、Mの約数を探す
Q = math.floor(math.sqrt(M)) #sqrt。解の探索範囲を絞るのに使う

# Mでないなら高々sqrt(M)


if P <= Q:
  # P=M/Nから1つずつ下がって探索
  for x in range(P, 0, -1):
    # print(x)
    if M % x == 0:
      print(x)
      break
elif P == M: # N=1
  print(M)
else:
  #1からQ=sqrt(M)まで増やす
  res = 1
  flag = 0
  for x in range(1, N, 1):
    # このときM/xはPより大きいことに注意
    if M % x == 0:
      res = x
  for x in range(N, Q+1, 1):
    if M % x == 0:
      print(M//x)
      flag = 1
      break
  if flag == 0:
    print(res)