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

import collections
import bisect
N, M, Q = map(int, input().split())
LR = [tuple(map(int, input().split())) for i in range(M)]


table = collections.defaultdict(list)
for L, R in LR:
    table[L].append(R)

for x in table:
    table[x].sort()

for _ in range(Q):
    p, q = map(int, input().split())
    ans = 0
    for i in range(p, q+1):
        ans += bisect.bisect_right(table[i], q)
    print(ans)


### FIXED CODE ###

import collections
import bisect
import sys
input = sys.stdin.readline
N, M, Q = map(int, input().split())
LR = [tuple(map(int, input().split())) for i in range(M)]
dp = [[0]*(N+1) for i in range(N+1)]

for L, R in LR:
    dp[L][R] += 1
for i in reversed(range(1, N)):
    for j in range(1, N+1):
        dp[i][j] += dp[i+1][j]

for i in range(1, N+1):
    for j in range(1, N+1):
        dp[i][j] += dp[i][j-1]


for _ in range(Q):
    p, q = map(int, input().split())
    print(dp[p][q])
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**6)
edges = {}
p = {}
def dfs(target_node, keisyo_point):
    global p
    p[target_node] += keisyo_point
    next_node = edges[target_node]
    if not next_node:
        return
    else:
        for next in next_node:
            edges[next].pop(edges[next].index(target_node))
            dfs(next, p[target_node])

def main():
    global edges, p
    n, q = map(int, input().split())
    edges = {e: [] for e in range(1, n+1)}
    for _ in range(n - 1):
        a, b = tuple(map(int, input().split()))
        edges[a].append(b)
        edges[b].append(a)
    p = {e: 0 for e in range(1, n+1)}
    for _ in range(q):
        p1, x1 = map(int, input().split())
        p[p1] += x1

    dfs(1, 0)
    for i1 in range(1, n + 1):
        print(p[i1], end=' ')

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
edges = {}
p = {}
done_nodes = set()

def dfs(target_node, keisyo_point):
    global p
    done_nodes.add(target_node)
    p[target_node] += keisyo_point
    next_node = edges[target_node]
    if not next_node:
        return
    else:
        for next in next_node:
            #edges[next].pop(edges[next].index(target_node))
            #dfs(next, p[target_node])
            if next in done_nodes:
                pass
            else:
                dfs(next, p[target_node])

def main():
    global edges, p
    n, q = map(int, input().split())
    edges = {e: [] for e in range(1, n+1)}
    for _ in range(n - 1):
        a, b = tuple(map(int, input().split()))
        edges[a].append(b)
        edges[b].append(a)
    p = {e: 0 for e in range(1, n+1)}
    for _ in range(q):
        p1, x1 = map(int, input().split())
        p[p1] += x1

    dfs(1, 0)
    for i1 in range(1, n + 1):
        print(p[i1], end=' ')

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

import collections
n = int(input())
a_list = list(map(int,input().split()))
c = collections.Counter(a_list)
for i in a_list:
  dic = c.copy()
  dic[i] = dic[i] - 1
  result = 0
  for s in dic.values():
    result += s*(s - 1)//2
  print(result)
    
  
  

### FIXED CODE ###

import collections
n = int(input())
a_list = list(map(int,input().split()))
c = collections.Counter(a_list)
result = 0
for i in c.values():
  result += i * (i - 1)//2

for a in a_list:
  print(result - c[a] + 1)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

class segtree:
    x_unit=0 # 単位元
    x_func=sum  # 関数
    def __init__(self,n):
        self.n=n
        self.x=[self.x_unit]*(2*n)
    def build(self, seq):
        for i,j in enumerate(seq, self.n):  # n番目からseqをx配列に移していく
            self.x[i] = j
        for i in range(self.n-1, 0, -1):
            self.x[i] = self.x_func([self.x[i*2], self.x[i*2+1]])
    def set_val(self,i,j): # 1点更新
        i += self.n
        self.x[i]=j
        while i>1:
            i//=2 # 更新後、木の上へと登っていくついでに更新
            self.x[i]=self.x_func([self.x[i*2], self.x[i*2+1]])
    def fold(self,l,r): # 区間[l, r)の最小値などを取得 
        l+=self.n
        r+=self.n
        val_l=self.x_unit
        val_r=self.x_unit
        while l<r:
            if l & 1: # lが奇数
                val_l=self.x_func([val_l,self.x[l]])
                l+=1 # 偶数に調節
            if r & 1: # rが奇数
                r-=1 # 開区間なので1個前は偶数番目の要素
                val_r=self.x_func([val_r,self.x[r]])
            l //= 2
            r //= 2
        return self.x_func([val_l,val_r])

from collections import defaultdict,deque
n,q=map(int, input().split())
c=list(map(int, input().split()))
c=[i-1 for i in c]
lr=[]
for i in range(q):
    l,r=map(int, input().split())
    lr.append((l-1,r-1))
lrsort=sorted(lr, key=lambda x:x[0])
lrsort=sorted(lr, key=lambda x:x[1])
lrsort=deque(lrsort)
#print(lrsort)
goodpos=[-1]*n
isgood=[0 for x in range(n)]
d=defaultdict(int)
s=0
seg=segtree(n)
seg.build(isgood)

while lrsort:
    l,r=lrsort.popleft()
    for i in range(s,r+1):
        if goodpos[c[i]]!=-1:
            seg.set_val(goodpos[c[i]],0)
        goodpos[c[i]]=i
        seg.set_val(i,1)
    s=r+1
    d[(l,r)]=seg.fold(l,r+1)

for l,r in lr:
    print(d[(l,r)])

### FIXED CODE ###

import sys
input = sys.stdin.readline
# Binary Indexed Tree (Fenwick Tree)
class BIT:
    def __init__(self, n):
        self.n = n
        self.data = [0]*(n+1)
        self.el = [0]*(n+1)
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.data[i]
            i -= i & -i
        return s
    def add(self, i, x):
        # assert i > 0
        self.el[i] += x
        while i <= self.n:
            self.data[i] += x
            i += i & -i
    def get(self, i, j=None):
        if j is None:
            return self.el[i]
        return self.sum(j) - self.sum(i)

n,q=map(int,input().split())
c=list(map(int,input().split()))
ques=[]
from collections import defaultdict
ans=defaultdict(int)
for _ in range(q):
    l,r=map(int,input().split())
    ques.append((l,r))

sortques=sorted(ques, key=lambda x:x[1])

good=BIT(n+1)
goodind=[-1]*n
last=0
for x in range(q):
    l,r=sortques[x]
    if last!=r:
        for i in range(last, r):
            if goodind[c[i]-1]==-1:
                goodind[c[i]-1]=i
                good.add(i+1, 1)
            else:
                j=goodind[c[i]-1]
                good.add(j+1, -1)
                goodind[c[i]-1]=i
                good.add(i+1, 1)
    ans[(l,r)]=good.get(l-1,r)
    last=r

for i in range(q):
    print(ans[ques[i]])
### BUGGY CODE ###

N = input()
a_list = list(map(int, input().split()))
b_list = list(map(int, input().split()))

if all([a >= b for a, b in zip(a_list, b_list)]):
    # すべての準備度が必要度を上回っている場合
    print(0)
else:
    # 準備度が足りていない試験がある場合
    if sum(a_list) < sum(b_list):
        # そもそも準備度の総量が足りない場合
        print(-1)
    else:
        # 準備度を移動すれば受かる場合
        # 一番数の大きいところから足りていないところに割り振る戦略
        # a_listをcopy
        c_list = [a for a in a_list]
        # 準備度の余裕をリストに格納
        diff_list = [c - b for c, b in zip(c_list, b_list)]
        # 一度減算し始めたら対象が0になるまで続ける
        selected_biggest_idx = diff_list.index(max(diff_list))
        while not all([c >= b for c, b in zip(c_list, b_list)]):
            if diff_list[selected_biggest_idx] == 0:
                selected_biggest_idx = diff_list.index(max(diff_list))
            min_idx = diff_list.index(min(diff_list))
            # 最大と最小で移し替えを行う
            if diff_list[selected_biggest_idx] < abs(diff_list[min_idx]):
                # 足りていない値のほうが大きい場合
                c_list[selected_biggest_idx] -= diff_list[selected_biggest_idx]
                c_list[min_idx] += diff_list[selected_biggest_idx]
            else:
                # 足りていない値のほうが小さい場合
                c_list[selected_biggest_idx] -= abs(diff_list[min_idx])
                c_list[min_idx] += abs(diff_list[min_idx])
            # diff_listを更新
            diff_list = [c - b for c, b in zip(c_list, b_list)]
        result_count = len([1 for a, c in zip(a_list, c_list) if a != c])
        print(result_count)



### FIXED CODE ###

import numpy as np

N = input()
a_list = np.array(list(map(int, input().split())))
b_list = np.array(list(map(int, input().split())))

#  # すべての準備度が必要度を上回っている場合
#  if all([a >= b for a, b in zip(a_list, b_list)]):
#      print(0)
#  # 準備度が足りていない試験がある場合
#  else:
# そもそも準備度の総量が足りない場合
if sum(a_list) < sum(b_list):
    print(-1)
else:
    # 準備度を移動すれば受かる場合
    # 一番数の大きいところから足りていないところに割り振る戦略
    # a_listをcopy
    # 準備度の余裕をリストに格納
    diff_list = a_list - b_list
    # 昇順にソート
    diff_list.sort()
    start = 0
    end = -1
    current_value = diff_list[end]
    while diff_list[start] < 0:
        # 最大値から減算
        current_value += diff_list[start]
        while current_value < 0:
            end -= 1
            current_value += diff_list[end]
        start += 1
    if start == 0:
        print(0)
    else:
        print(start - end)
### BUGGY CODE ###

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

### FIXED CODE ###

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

from collections import Counter
N = int(input())
A = list(map(int,input().split()))
c = Counter(A)

NMAX=2*10**5

tmp = [0]*(NMAX+1)
tmp2 = [0]*(NMAX+1)
for n in c:
    k= c[n]-1
    tmp[n] = (c[n] * (c[n] - 1) // 2)
    tmp2[n] = (k * (k - 1) // 2)

for a in A:
    sum = 0
    for i in c:
        if a ==i:
            sum += tmp2[i]
        else:
            sum += tmp[i]
    print(sum)



### FIXED CODE ###

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

import collections 
c=collections.Counter(A)
sum=0
for i in c:
  sum+=c[i]*(c[i]-1)//2  
for a in A:
  print(sum - c[a]*(c[a]-1)//2 + (c[a]-1)*(c[a]-2)//2)
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
b = []
if n % 2 == 0:
    for i in range(n):
        if i % 2 == 0:
            b.append(a[i])
        else:
            b.insert(0,a[i])
else:
    for i in range(n):
        if i % 2 != 0:
            b.append(a[i])
        else:
            b.insert(0,a[i])
for i in b:
    print(i, end=" ")

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
left = []
right = []
if n % 2 == 0:
    for i in range(1,n+1):
        if i % 2 == 0:
            left.append(a[i-1])
        else:
            right.append(a[i-1])
else:
    for i in range(1,n+1):
        if i % 2 != 0:
            left.append(a[i-1])
        else:
            right.append(a[i-1])
left.reverse()
for i in left:
    print(i,end=' ')
for i in right:
    print(i,end=' ')
### BUGGY CODE ###

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

x = input()

for i in range(0, int(len(x)/2)):
    x = x.replace("ST", "")
    if len(x) == 0:
        break

print(len(x))


### FIXED CODE ###

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

x = input()

# ペアになっていないSの数（ペアができたら-1）
sc = 0
# ペアにならなかったTの数
tc = 0

for c in x:
    if c == 'S':
        sc += 1
    elif sc >= 1:
        sc -= 1
    else:
        tc += 1

print(sc + tc)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(100000)

def visit_tree(now, num):
    visited[now] = num
    for i in range(len(tree[now])):
        if not visited[tree[now][i]]:
            visit_tree(tree[now][i], num)

n, m = map(int, input().split())
tree = [[] for _ in range(n)]
for i in range(m):
    x, y, z = map(int, input().split())
    tree[x - 1].append(y - 1)
    tree[y - 1].append(x - 1)

visited = [0 for _ in range(n)]
num = 0
for i in range(n):
    if not visited[i]:
        num += 1
        visit_tree(i, num)

print(num)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10000000)

def visit_tree(now, num):
    visited[now] = num
    for i in range(len(tree[now])):
        if not visited[tree[now][i]]:
            visit_tree(tree[now][i], num)

n, m = map(int, input().split())
tree = [[] for _ in range(n)]
for i in range(m):
    x, y, z = map(int, input().split())
    tree[x - 1].append(y - 1)
    tree[y - 1].append(x - 1)

visited = [0 for _ in range(n)]
num = 0
for i in range(n):
    if not visited[i]:
        num += 1
        visit_tree(i, num)

print(num)
### BUGGY CODE ###

n = int(input())
nums = list(map(int,input().split()))
nums.sort()
unique = []
dupes = {}
for i in range(len(nums)):
  flag = 0
  for j in range(len(unique)):
    if i==j:
      continue
    if nums[i]%unique[j] == 0:
      if nums[i] == unique[j]:
        dupes[nums[i]] = 1
      flag = 1
      break
  if flag == 0:
    unique.append(nums[i])
for i in unique:
  if i in dupes:
    unique.remove(i)
print(len(unique))

### FIXED CODE ###

n = int(input())
nums = list(map(int,input().split()))
nums.sort()
ans = 0
cnt = {}
flag = [0]*1000005
for i in nums:
  cnt[i] = cnt.get(i,0) + 1

for i in nums:
  if flag[i] == 0 and cnt[i] == 1:
    ans += 1
  if flag[i] == 1:
    continue
  for j in range(i,1000001,i):
    flag[j] = 1

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

import collections
h, w = map(int, input().split())
a = [list(input()) for _ in range(h)]

queue = collections.deque()

ans = 0


def bfs(y, x, cnt):
    if (y < 0 or h <= y or x < 0 or w <= x or a[y][x] == '#'):
        return
    #print(y, x, cnt)
    a[y][x] = '#'
    queue.append([y + 1, x, cnt+1])
    queue.append([y - 1, x, cnt+1])
    queue.append([y, x+1, cnt+1])
    queue.append([y, x - 1, cnt+1])


for i in range(h):
    for j in range(w):
        if (a[i][j] == '#'):
            queue.append([i+1, j, 0])
            queue.append([i-1, j, 0])
            queue.append([i, j+1, 0])
            queue.append([i, j-1, 0])

while (len(queue) > 0):
    l = queue.popleft()
    # print(l)
    ans = max(ans, l[2])
    bfs(l[0], l[1], l[2])

print(ans)

### FIXED CODE ###

from collections import deque
import copy
 
def main():
    h, w = map(int, input().split())
    a = [[j == "#" for j in input()] for _ in range(h)]
 
 
    # スタート地点をqueueに追加
    que = deque([(i, j) for i in range(h) for j in range(w) if a[i][j]])
 
    count = 0
    while True:
        count += 1
        nque = deque()
        while que:
            y, x = que.popleft()
            if x > 0 and not a[y][x-1]:
                a[y][x-1] = True
                nque.append((y,x-1))
            if x < w-1 and not a[y][x+1]:
                a[y][x+1] = True
                nque.append((y,x+1))
            if y > 0 and not a[y-1][x]:
                a[y-1][x] = True
                nque.append((y-1,x))
            if y < h-1 and not a[y+1][x]:
                a[y+1][x] = True
                nque.append((y+1,x))
 
        if nque:
            que = copy.copy(nque)
        else:
            break
 
    print(count - 1)
 
if __name__ == "__main__":
    main()
### BUGGY CODE ###

N=int(input())
S=input()
w=ans=9**9
for i in range(N):
    e=S[:i].count("W")
    w=S[i:].count("E")
    ans=min(ans,e+w)
    if w==0:break
print(ans)

### FIXED CODE ###

N=int(input())
S=input()
e=0
ans=w=S.count("E")
for i in S:
    if i=="E":w-=1
    else: e+=1
    ans=min(ans,e+w)
print(ans)
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
#print(n)
#print(a)
count=0
i=0
flag=True
while(flag):
    flag=False
    for i in range(n):
        if(a[i]%2==0):
            #print(i)
            a[i]=a[i]/2
            count+=1
            flag=True
        else:
            a[i]=a[i]*3
print(count)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
#print(n)
#print(a)
count=0
flag=True
while(flag):
    flag=False
    for i in range(n):
        while(a[i]%2==0):
            #print(i)
            #a=list(map(lambda x:x*3,a))
            a[i]=int(a[i]/2)
            #print(a)
            count+=1
            flag=True
            #break
print(count)
#たぶんリスト全部に3かけて該当を６で割ればよさそう
#３倍する必要がない
### BUGGY CODE ###

S = list(input())

R = [[None]*10 for i in range(13)]
for i in range(13):
    for j in range(10):
        R[i][j] = (10*i+j) % 13
        
Q = [[] for i in range(13)]
for j in range(10):
    for i in range(13):
        Q[R[i][j]] += [[i,j]]

dp = [[0]*13 for i in range(len(S)+1)]
dp[0][0] = 1

for i in range(len(S)):
    for j in range(13):
        if S[i]!='?':
            dp[i+1][j] += dp[i][Q[j][int(S[i])][0]]
        else:
            for k in range(10):
                dp[i+1][j] += dp[i][Q[j][k][0]]
                
print(dp[len(S)][5]%1000000007)

### FIXED CODE ###

S = list(input())
for i in range(len(S)):
    if S[i] != '?':
        S[i] = int(S[i])
    else:
        S[i] = -1

R = [[None]*10 for i in range(13)]
for i in range(13):
    for j in range(10):
        R[i][j] = (10*i+j) % 13

Q = [[] for i in range(13)]
for j in range(10):
    for i in range(13):
        Q[R[i][j]] += [[i,j]]

dp = [[0]*13 for i in range(len(S)+1)]
dp[0][0] = 1

for i in range(len(S)):
    for j in range(13):
        if S[i]!=-1:
            dp[i+1][j] += dp[i][Q[j][S[i]][0]]%1000000007
        else:
            for k in range(10):
                dp[i+1][j] += dp[i][Q[j][k][0]]%1000000007

print(dp[len(S)][5]%1000000007)
### BUGGY CODE ###

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

A.sort(reverse=True)
ans = 0
tmp = 0
for i in range(N):
    if i == 0:
        continue
    elif i == 1:
        ans += A.pop(0)
    elif i % 2 == 0:
        tmp = A.pop(0)
        ans += tmp
    else:
        ans += tmp
print(ans)

### FIXED CODE ###

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

A.sort()
ans = 0
tmp = 0
for i in range(N):
    if i == 0:
        continue
    elif i == 1:
        ans += A.pop()
    elif i % 2 == 0:
        tmp = A.pop()
        ans += tmp
    else:
        ans += tmp
print(ans)
### BUGGY CODE ###

N = int(input())
ls = [0]*(N)
n = 1
while n <= N-1:
  k = 1
  tmp = 0
  while k**2 <= n:
    if n % k == 0:
      if k ** 2 == n:
        tmp += 1
      else:
        tmp += 2
    k += 1
  ls[n] = tmp
  n += 1
print(sum(ls))



### FIXED CODE ###

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

import itertools
n,k=map(int,input().split())
def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)
def combination(n, r, mod=10**9+7):
    r = min(r, n-r)
    res = 1
    for i in range(r):
        res = res * (n - i) * modinv(i+1, mod) % mod
    return res
a=list(map(int,input().split()))
a.sort()
b=a[::-1]
#print(a,b)
ans=0
for i in range(k-1,n):
    ans+=(a[i]-b[i])*(combination(i, k-1, mod=10**9+7))
print(ans%(10**9+7))


### FIXED CODE ###

n,k=map(int,input().split())
def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)
def combination(n, r, mod=10**9+7):
    r = min(r, n-r)
    res = 1
    for i in range(r):
        res = res * (n - i) * modinv(i+1, mod) % mod
    return res

mod=10**9+7
f=[1]
for i in range(n):f+=[f[-1]*(i+1)%mod]
def comb(a,b):
    return f[a]*pow(f[b],mod-2,mod)*pow(f[a-b],mod-2,mod)%mod

a=list(map(int,input().split()))
a.sort()
b=a[::-1]
#print(a,b)
ans=0
for i in range(k-1,n):
    ans+=((a[i]-b[i])*(comb(i,k-1)))%(10**9+7)
print(ans%(10**9+7))
### BUGGY CODE ###

import sys
import math
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def make_grid(h, w, num): return [[int(num)] * w for _ in range(h)]


# Nの素因数分解を辞書で返す
def prime_fact(n):
    root = int(math.sqrt(n))
    prime_dict = {}
    for i in range(2, root+1):
        cnt = 0
        for j in range(root+1):
            if n % i == 0 and n != 0:
                cnt += 1
                n = n // i
            else:
                break
        if cnt:
            prime_dict[i] = cnt
    if n != 1:
        prime_dict[n] = 1
    return prime_dict


def main():
    N = NI()
    A = NLI()
    L = {}
    primes_a = {}
    for a in A:
        prime_a = prime_fact(a)
        primes_a[a] = prime_a
        for p, n in prime_a.items():
            L.setdefault(p, 0)
            L[p] = max(L[p], n)
    ans = 0
    l = 1
    for p, n in L.items():
        l = l * pow(p, n, MOD) % MOD

    for i, a in enumerate(A):
        ans += l * pow(a, -1, MOD) % MOD
    print(ans % MOD)



if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
import math
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def make_grid(h, w, num): return [[int(num)] * w for _ in range(h)]


# Nの素因数分解を辞書で返す
def prime_fact(n):
    root = int(math.sqrt(n))
    prime_dict = {}
    for i in range(2, root+1):
        cnt = 0
        for j in range(root+1):
            if n % i == 0 and n != 0:
                cnt += 1
                n = n // i
            else:
                break
        if cnt:
            prime_dict[i] = cnt
    if n != 1:
        prime_dict[n] = 1
    return prime_dict


def main():
    N = NI()
    A = NLI()
    L = {}
    primes_a = {}
    for a in A:
        prime_a = prime_fact(a)
        primes_a[a] = prime_a
        for p, n in prime_a.items():
            L.setdefault(p, 0)
            L[p] = max(L[p], n)
    ans = 0
    l = 1
    for p, n in L.items():
        l = l * pow(p, n, MOD) % MOD

    for i, a in enumerate(A):
        ans += l * pow(a, MOD-2, MOD) % MOD
    print(ans % MOD)



if __name__ == "__main__":
    main()
### BUGGY CODE ###

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


def divisor(num):
    opside = num
    i = 2
    div = [1, opside]
    while i <= opside:
        if num % i == 0:
            opside = num // i
            if i == opside:
                div.append(i)
            elif opside <= i:
                break
            else:
                div.append(i)
                div.append(opside)
        i += 1
    div.sort()
    return div


ans = 0
for i in divisor(m):
    if n <= m // i:
        ans = i
    else:
        break
print(ans)

### FIXED CODE ###

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


def divisor(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


ans = 0
for i in divisor(m):
    if n <= m // i:
        ans = i
    else:
        break
print(ans)
### BUGGY CODE ###

def main():
    import sys
    import time
    start=time.time()
    K=int(sys.stdin.readline())
    if K%2==0:
        print(-1)
        return

    L=[7%K]
    L2=[7%K]
    if L[0]==0:
        print(1)
        return

    idx=0
    while True:
        L2.append((L2[idx]*10)%K)
        L.append((L[idx]+L2[idx+1])%K)
        if L[-1]==0:
            print(len(L))
            return
        idx+=1

        if start-time.time()>=1.2:
            print(-1)
            return
main()

### FIXED CODE ###

def main():
    import sys
    import time
    start=time.time()
    K=int(sys.stdin.readline())
    if K%2==0:
        print(-1)
        return

    L=[7%K]
    L2=[7%K]
    if L[0]==0:
        print(1)
        return

    idx=0
    while True:
        L2.append((L2[idx]*10)%K)
        L.append((L[idx]+L2[idx+1])%K)
        if L[-1]==0:
            print(len(L))
            return
        idx+=1

        if time.time()-start>=1.5:
            print(-1)
            return
main()