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

from collections import deque

def bfs(sx, sy, gx, gy):
    dist = [[-1]*W for _ in range(H)]
    dist[sx][sy] = 0
    q = deque([(sx, sy)])
    
    while q:
        cx, cy = q.popleft()
        
        for nx, ny in [(cx-1, cy), (cx+1, cy), (cx, cy-1), (cx, cy+1)]:
            if not (0<=nx<H and 0<=ny<W):
                continue
            
            if S[nx][ny]=='.' and dist[nx][ny]==-1:
                dist[nx][ny] = dist[cx][cy]+1
                q.append((nx, ny))
    
    return dist[gx][gy]

H, W = map(int, input().split())
S = [list(input()) for _ in range(H)]
ans = -10**18

for i in range(H):
    for j in range(W):
        for k in range(H):
            for l in range(W):
                if S[i][j]!='#' and S[k][l]!='#':
                    ans = max(ans, bfs(i, j, k, l))

print(ans)

### FIXED CODE ###

from collections import deque

def bfs(sx, sy):
    dist = [[-1]*W for _ in range(H)]
    dist[sx][sy] = 0
    q = deque([(sx, sy)])
    res = 0
    
    while q:
        cx, cy = q.popleft()
        
        for nx, ny in [(cx-1, cy), (cx+1, cy), (cx, cy-1), (cx, cy+1)]:
            if not (0<=nx<H and 0<=ny<W):
                continue
            
            if S[nx][ny]=='.' and dist[nx][ny]==-1:
                dist[nx][ny] = dist[cx][cy]+1
                q.append((nx, ny))
                res = max(res, dist[nx][ny])
    
    return res

H, W = map(int, input().split())
S = [input() for _ in range(H)]
ans = 0

for i in range(H):
    for j in range(W):
        if S[i][j]=='.':
            ans = max(ans, bfs(i, j))

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

from functools import reduce

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


res = [0] * (n-k+1)
res[0] = reduce(lambda x, y: x*y , A[0:k+1])

for i in range(1, n-k+1):
    res[i] = res[i-1]//A[i-1]*A[i+k-1]

for j in range(n-k):
    ans = 'Yes' if res[j] < res[j+1] else 'No'
    print(ans)



### FIXED CODE ###

from functools import reduce

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

for i in range(0, n-k):
    print('Yes' if A[i] < A[i+k] else 'No')
### BUGGY CODE ###

n,m=map(int,input().split())
from collections import deque
que=deque(map(int,input().split()))
for _ in range(m):
    b,c=map(int,input().split())
    que=sorted(que)
    for i in range(b):
        if que[0]<c:
            que.pop(0)
            que.append(c)
        else:
            break

print(sum(que))


### FIXED CODE ###

n,m=map(int,input().split())
List=sorted(list(map(int,input().split())))
s=[]
for _ in range(m):
    s.append(list(map(int,input().split())))
s.sort(key=lambda x: x[1], reverse=True)

ans=0
j=0
for i in range(m):
    if j>=n or s[i][1]<=List[j]:
        break
    while j<n and s[i][0]>0 and s[i][1]> List[j]:
        ans+=s[i][1]
        s[i][0]-=1
        j+=1
if j>=n:
    print(ans)
else:
    print(ans+sum(List[j:]))
### BUGGY CODE ###

import math

N = int(input())

T,A = map(int, input().split())
rlt = T+A
for _ in range(N-1):
  t,a = map(int, input().split())
  i = math.ceil(rlt/(t+a))
  while i*t < T or i*a < A:
    i += 1
  T = i*t
  A = i*a
  
print(T+A) 

### FIXED CODE ###

import math

N = int(input())

T,A = map(int, input().split())
for _ in range(N-1):
  t,a = map(int, input().split())
  if T % t == 0:
    i = T // t
  else:
    i = T // t + 1
  if A % a == 0:
    j = A // a
  else:
    j = A // a + 1
  k = max(i,j)
  T = k*t
  A = k*a
  
print(T+A)
### BUGGY CODE ###

import sys

stdin = sys.stdin

ns = lambda : stdin.readline().rstrip()
ni = lambda : int(ns())
na = lambda : list(map(int, stdin.readline().split()))
sys.setrecursionlimit(10 ** 7)

def main():
    s = ns()
    Q = ni()

    for _ in range(Q):
        T = stdin.readline().split()
        if T[0] == "1":
            s = s[::-1]
        else:
            if T[1] == "1":
                s = T[2] + s
            else:
                s += T[2]
    print(s)

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys

stdin = sys.stdin

ns = lambda : stdin.readline().rstrip()
ni = lambda : int(ns())
na = lambda : list(map(int, stdin.readline().split()))
sys.setrecursionlimit(10 ** 7)

def main():
    s = ns()
    Q = ni()

    T1 = 0
    FrontS = ""
    BackS = ""
    for _ in range(Q):
        T = stdin.readline().split()
        if T[0] == "1":
            FrontS, BackS = BackS, FrontS
            T1 += 1
        else:
            if T[1] == "1":
                FrontS += T[2]
            else:
                BackS += T[2]
                
    FrontS = FrontS[::-1]

    if T1 % 2 == 0:
        print(FrontS + s + BackS)
    else:
        print(FrontS + s[::-1] + BackS)

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

import sys
input = sys.stdin.readline
import numpy as np

MOD = 10 ** 9 + 7
S = input().rstrip()

ten = np.zeros(13, dtype=np.int64)
ten[:10] += 1
add_all = [ten]
for _ in range(5):
  add_all.append(add_all[-1][np.arange(0,52,4)%13])

add_single = [[x * 10 ** i for x in range(10)] for i in range(6)]

dp = np.zeros(13, dtype = np.int64)
dp[0] = 1
constant_term = 0
for i,s in enumerate(S[::-1]):
  if s == '?':
    dp = np.convolve(dp, add_all[i%6])
    dp[:12] += dp[13:25]
    dp = dp[:13] % MOD
  else:
    constant_term += add_single[i%6][int(s)]

    
dp = np.roll(dp, constant_term)
print(dp[5])


### FIXED CODE ###

MOD = 10 ** 9 + 7
S = input()

dp = [0] * 13
dp[0] = 1

for s in S:
  prev = [x for x in dp]
  dp = [0] * 13
  if s == '?':
    add = range(10)
  else:
    add = [int(s)]
  for i in range(13):
    for x in add:
      dp[(10*i+x)%13] += prev[i]
  dp = [x % MOD for x in dp]
  
print(dp[5])
### BUGGY CODE ###

r,g,b,n = map(int,input().split())

res=0
tmp=n
tmp1=0
re=n//r+1
ge=n//g+1

for i in range(re):
	tmp = tmp - i*r
	tmp1 = tmp
	for j in range(ge):
		tmp1 = tmp - j*g
		if tmp1 >= 0 and tmp1%b==0:
			res = res + 1
			#print(i, j, int(tmp1/t2[2]))
		tmp1 = tmp
	tmp=n

print(res)

### FIXED CODE ###

r,g,b,n = map(int,input().split())

res=0
tmp=n
tmp1=0
re=n//r+1
ge=n//g+1

for i in range(re):
	tmp = tmp - i*r
	tmp1 = tmp
	for j in range(ge):
		tmp1 = tmp - j*g
		if tmp1 >= 0 and tmp1%b==0:
			res = res + 1
			#print(i, j, int(tmp1/t2[2]))
		tmp1 = tmp
	tmp=n

print(res)
### BUGGY CODE ###

def trim():
    num=[]
    N=[input() for _ in range(8)]
    for x in range(8):
        for y in range(8):
            if N[y][x]=="1":
                if not num:
                    refer=(x,y)
                num.append((x,y))
    num=[(x-refer[0],y-refer[1]) for x,y in num]
    return num
def point(point):
    if point==[(0,0),(0,1),(1,0),(1,1)]:print("A")
    if point==[(0,0),(0,1),(0,2),(0,3)]:print("B")
    if point==[(1,0),(2,0),(3,0),(4,0)]:print("C")
    if point==[(0,0),(0,1),(1,-1),(1,0)]:print("D")
    if point==[(0,0),(1,0),(1,1),(2,1)]:print("E")
    if point==[(0,0),(0,1),(1,1),(1,2)]:print("F")
    if point==[(0,0),(1,-1),(1,0),(2,-1)]:print("G")
while True:
    try:
        point(trim)
    except:break


### FIXED CODE ###

def trim(N):
    num=[]
    for x in range(8):
        for y in range(8):
            if N[y][x]=="1":
                if not num:
                    refer=(x,y)
                num.append((x,y))
    num=[(x-refer[0],y-refer[1]) for x,y in num]
    return num
def points(point):
    if point==[(0,0),(0,1),(1,0),(1,1)]:print("A")
    if point==[(0,0),(0,1),(0,2),(0,3)]:print("B")
    if point==[(0,0),(1,0),(2,0),(3,0)]:print("C")
    if point==[(0,0),(0,1),(1,-1),(1,0)]:print("D")
    if point==[(0,0),(1,0),(1,1),(2,1)]:print("E")
    if point==[(0,0),(0,1),(1,1),(1,2)]:print("F")
    if point==[(0,0),(1,-1),(1,0),(2,-1)]:print("G")
while True:
    N=[input() for _ in range(8)]
    points(trim(N))
    try:
        input()
    except:break
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10 ** 9)

N, Q = [int(_) for _ in input().split()]

edges = [[] for _ in range(N + 1)]
for i in range(N - 1):
    a, b = [int(_) for _ in input().split()]
    edges[a].append(b)
    edges[b].append(a)

P = [0] * (N + 1)

for q in range(Q):
    p, x = [int(_) for _ in input().split()]
    P[p] += x


def f(v, parent=0):
    P[v] += P[parent]

    for next_v in edges[v]:
        if next_v == parent: continue
        f(next_v, v)


f(1)
print(*[P[i] for i in range(1, N + 1)])


### FIXED CODE ###

import sys
from collections import deque

sys.setrecursionlimit(10 ** 9)
input = sys.stdin.readline

N, Q = [int(_) for _ in input().split()]

edges = [[] for _ in range(N + 1)]
for i in range(N - 1):
    a, b = [int(_) for _ in input().split()]
    edges[a].append(b)
    edges[b].append(a)

P = [0] * (N + 1)

for q in range(Q):
    p, x = [int(_) for _ in input().split()]
    P[p] += x

que = deque()
que.append((1, 0))

while que:
    v, parent = que.popleft()
    P[v] += P[parent]
    for next_v in edges[v]:
        if next_v == parent: continue
        que.append((next_v, v))

# def f(v, parent=0):
#     P[v] += P[parent]
#
#     for next_v in edges[v]:
#         if next_v == parent: continue
#         f(next_v, v)
#
#
# f(1)
print(*[P[i] for i in range(1, N + 1)])
### BUGGY CODE ###

N = int(input())

import heapq 
from collections import defaultdict

def is_prime(q):
    q = abs(q)
    if q == 2: return True
    if q < 2 or q&1 == 0: return False
    return pow(2, q-1, q) == 1

heap = [2]
cand = 3
heapq.heapify(heap)
ans = 0
dict_prime = defaultdict(int)
# dict_prime[2] = 2
cnt = 0
if is_prime(N):
    ans = 1
else:
    while(1):
        # print(N)
        # cnt += 1
        # if cnt > 10:break

        sub = heapq.heappop(heap)
        # print(sub)
        # print(cand)
        # print(heap)
        # print(cand)
        # print(heapq)
        if N < sub:
            # print(N,sub)
            # print("a")
            break
        if N % sub == 0:
            N = N // sub
            ans += 1
            if sub not in dict_prime:
                dict_prime[sub] = sub
                dict_prime[sub*sub] = sub
            else:
                dict_prime[sub*dict_prime[sub]] = dict_prime[sub]
                # print("a")
            heapq.heappush(heap, sub*dict_prime[sub])

        while(1):
            if is_prime(cand) and cand not in dict_prime:
                heapq.heappush(heap,cand)
                cand += 1
                break
            else:
                cand += 1


# print()
print(ans)
    



# sqrt(N)以下の素数の集合を求める
# heapqにいれる
# 一番小さいので割れなかったらスルー割れたら累乗してheapqへ入れる

# def get_primes(n):
#     ans = []
#     for i in range(1,n+1):
#         if is_prime(i):
#             ans.append(i)
#     return ans


# prime = get_primes(int(N**(1/2)))






### FIXED CODE ###

N = int(input())

import heapq 





def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i,i, cnt])

    if temp!=1:
        arr.append([temp,temp, 1])

    if arr==[]:
        arr.append([n,n,1])

    return arr

# for N in range(1,100000):
# N = 288
# print(N)

heap = factorization(N) 
# print(heap)
# print(heap)
heapq.heapify(heap)
ans = 0

while(heap):
    # print(heap)
    if N == 1:
        break
    sub,prime,cnt = heapq.heappop(heap)
    if N < sub:
        break
    if N % sub == 0:
        N = N // sub
        ans += 1
        if cnt > 0:
            cnt -= 1
            sub *= prime
            heapq.heappush(heap, [sub,prime,cnt])

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

n, q = map(int, input().split())
s = input()
list = [0]*q

for i in range(q):
    start,end=[int(i) for i in input().split()]
    list[i] = s.count("AC", start-1, end)

for i in list:
    print(i)



### FIXED CODE ###

n, q = map(int, input().split())
s = input()
x = [0]*(n+1)

for i in range(n):
    x[i+1] = x[i] + (1 if s[i:i+2] == "AC" else 0)

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

N = int(input())
A = list(map(int, input().split(' ')))
result = 0
mod = 10 ** 9 +7
for i in range(N):
  for j in range(i+1, N):
    calc = result + A[i] * A[j]
    result = calc - calc // mod * mod
print(result)

### FIXED CODE ###

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

mod = 10 ** 9 +7
amount = sum(A)
calc = []
for i in range(N - 1):
  amount = amount - A[i]
  calc.append(amount)

for i in range(N - 1):
  calc[i] *= A[i]

print(sum(calc) % mod)
### BUGGY CODE ###

from functools import lru_cache

S = "0" + input()

digits = [int(c) for c in S.rstrip("0")]


@lru_cache(maxsize=None)
def f(sign, place):
    if place == len(digits) - 1:
        if sign > 0:
            exact = digits[place]
        else:
            exact = 10 - digits[place]
        return exact

    if sign > 0:
        exact = digits[place]
        overpay = exact + 1  # Overpaying flips the sign of the balance
    else:
        assert sign < 0
        exact = 10 - digits[place] - 1
        overpay = exact + 1

    return min(exact + f(sign, place + 1), overpay + f(-sign, place + 1))


for sign in [-1, 1]:
    for place in reversed(range(len(digits))):
        f(sign, place)

print(f(1, 0))


### FIXED CODE ###

S = "0" + input()

digits = [int(c) for c in S.rstrip("0")]
N = len(digits)

# Track number of bills necessary to create digits[:i]
# Can either pay exact or overpay by one bill to flip the sign of the balance
dpPos = [None] * len(digits)
dpNeg = [None] * len(digits)

dpPos[-1] = digits[-1]
dpNeg[-1] = 10 - digits[-1]

for place in reversed(range(len(digits) - 1)):
    # Positive balance case
    exact = digits[place]
    overpay = exact + 1
    dpPos[place] = min(exact + dpPos[place + 1], overpay + dpNeg[place + 1])
    # Negative balance case
    exact = 10 - digits[place] - 1
    overpay = exact + 1
    dpNeg[place] = min(exact + dpNeg[place + 1], overpay + dpPos[place + 1])
print(dpPos[0])
### BUGGY CODE ###


def Get_nC2(n):
    return int(n*(n-1) / 2);


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

for a_i in A_i:
    cnt = 0
    for j in range(min(A_i), max(A_i)+1):
        j_cnt = A_i.count(j)
        if a_i == j:
            j_cnt -= 1

        cnt += Get_nC2(j_cnt)

    print(cnt)


### FIXED CODE ###

from collections import Counter

def Get_nC2(n):
    return int(n*(n-1) / 2)


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

c = Counter(A_i)


total = sum(list(map(Get_nC2, c.values())))

for a_i in A_i:
    result =  total - Get_nC2(c[a_i]) + Get_nC2(c[a_i]-1)
    print(result)
### BUGGY CODE ###

def main():
    N, P = map(int, input().split())

    left = 0
    right = 10**12
    while left + 1 < right:
        mid = (left + right) // 2
        if mid**N <= P:
            left = mid
        else:
            right = mid

    for j in range(left, 0, -1):
        if P % j**N == 0:
            print(j)
            break


main()


### FIXED CODE ###

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5 // 1)) + 1):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            arr.append([i, cnt])

    if temp != 1:
        arr.append([temp, 1])

    if arr == []:
        arr.append([n, 1])

    return arr


def main():
    N, P = map(int, input().split())
    A = factorization(P)

    B = []
    for a, b in A:
        if b >= N:
            B.append((a, b // N))

    ans = 1
    for a, b in B:
        ans *= a**b
    print(ans)


main()
### BUGGY CODE ###

import sys
from collections import *

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")

def main():
    def dfs(u=0):
        if not to[u]:
            dp[u] = [[inv2, inv2, 0]]
            return
        dpu = []
        for v in to[u]:
            dfs(v)
            v = utou[v]
            if not dpu:
                dpu = dp[v]
                utou[u] = v
                continue
            dpv = dp[v]
            if len(dpu) < len(dpv):
                dpu, dpv = dpv, dpu
                utou[u] = v
            for d in range(len(dpv)):
                dpu[d][2] = (dpu[d][2] * sum(dpv[d]) + dpv[d][2] * sum(dpu[d])
                             - dpu[d][2] * dpv[d][2] + dpu[d][1] * dpv[d][1]) % md
                dpu[d][1] = (dpu[d][0] * dpv[d][1] + dpu[d][1] * dpv[d][0]) % md
                dpu[d][0] = (dpu[d][0] * dpv[d][0]) % md
        for d in range(len(dpu)):
            dpu[d][0] = (dpu[d][0] + dpu[d][2]) % md
            dpu[d][2] = 0
        dpu.insert(0, [inv2, inv2, 0])

    md = 10 ** 9 + 7
    inv2 = pow(2, md - 2, md)
    to = defaultdict(list)
    n = int(input())
    pp = list(map(int, input().split()))
    for i, p in enumerate(pp):
        i += 1
        to[p].append(i)
    #print(to)
    utou = list(range(n + 1))
    dp = [[] for _ in range(n + 1)]
    dfs()
    #p2D(dp)
    # print(utou)
    root = utou[0]
    ans = 0
    for dpr in dp[root]:
        ans += dpr[1]
    ans %= md
    print((ans * pow(2, n + 1, md)) % md)

main()


### FIXED CODE ###

import sys

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")

def main():
    def dfs(u=0):
        def merge(dpu, dpv):
            vn = len(dpv)
            for d in range(-1, -1 - vn, -1):
                u0, u1, u2 = dpu[d]
                v0, v1, v2 = dpv[d]
                n0 = (u0 * v0) % md
                n1 = (u0 * v1 + u1 * v0) % md
                n2 = (u2 * (v0 + v1 + v2) + v2 * (u0 + u1) + u1 * v1) % md
                dpu[d] = (n0, n1, n2)

        # 葉の場合
        if len(to[u]) == 0:
            return [(inv2, inv2, 0)]
        # すべての子をマージ
        dpu = []
        mxlen=0
        for v in to[u]:
            dpv = dfs(v)
            #深さが2段以上あったらu2をu0に
            if not dpu:
                dpu = dpv
            else:
                if len(dpu) < len(dpv): dpu, dpv = dpv, dpu
                mxlen=max(mxlen,len(dpv))
                merge(dpu, dpv)
        for d in range(-1,-1-mxlen,-1):
            u0,u1,u2=dpu[d]
            dpu[d] = (u0 + u2, u1, 0)
        dpu.append((inv2, inv2, 0))
        return dpu

    md = 10 ** 9 + 7
    # 1/2のmod
    inv2 = pow(2, md - 2, md)
    n = int(input())
    to = [[] for _ in range(n+1)]
    pp = list(map(int, input().split()))
    for i, p in enumerate(pp, 1):
        to[p].append(i)
    # print(to)
    dp0 = dfs()
    # print(dp0)
    ans = sum(u1 for _, u1, _ in dp0)
    print((ans * pow(2, n + 1, md)) % md)

main()
### BUGGY CODE ###

import sys

sys.setrecursionlimit(1000000)

def mod_combination(n, k, mod):
    # nCk (mod m)
    def mod_permutation(n, k, mod):
        if n<=k:
            return 1
        else:
            return (n * mod_permutation(n-1,k,mod))%mod

    def mod_inv_permutation(k, mod):
        k, mod = int(k), int(mod)
        if k<=1:
            return 1
        else:
            return (pow(k,mod-2,mod) * mod_inv_permutation(k-1, mod))%mod

    return (mod_permutation(n,n-k,mod) * mod_inv_permutation(k, mod))%mod

n,a,b = map(int,input().split())
ans = (2**n - 1) 
k = mod_combination(n, a,10**9+7)
l = mod_combination(n, b,10**9+7)
ans -= k
ans -= l
ans %= 10**9+7
print(ans)

### FIXED CODE ###

n,a,b = map(int,input().split())
mod = 10**9+7
ans = pow(2,n,mod) - 1 
mod_inv = [0, 1] + [0] * (b+3)
for i in range(2, b+5):
    mod_inv[i] = - mod_inv[mod % i] * (mod // i) % mod
def comod(n, r, mod):
    ans = 1
    for i in range(r):
        ans *= (n-i) % mod
        ans *= mod_inv[i+1]
        ans %= mod
    return ans
ans -= comod(n,a,mod) + comod(n,b,mod)
print(ans % mod)
### BUGGY CODE ###

h, w = map(int, input().split())
a = [tuple(map(int, input().split())) for _ in range(h)]
b = [tuple(map(int, input().split())) for _ in range(h)]
c = [[a[i][j] - b[i][j] for j in range(w)] for i in range(h)]

dp = [[set() for _ in range(w)] for _ in range(h)]
dp[0][0].add(c[0][0])

for i in range(h):
    for j in range(w):
        for x in dp[i][j]:
            if i < h - 1:
                dp[i + 1][j].add(abs(x + c[i + 1][j]))
                dp[i + 1][j].add(abs(x - c[i + 1][j]))

            if j < w - 1:
                dp[i][j + 1].add(abs(x + c[i][j + 1]))
                dp[i][j + 1].add(abs(x - c[i][j + 1]))

print(min(dp[h - 1][w - 1]))


### FIXED CODE ###

import sys
input = sys.stdin.readline

h, w = map(int, input().split())
a = [tuple(map(int, input().split())) for _ in range(h)]
b = [tuple(map(int, input().split())) for _ in range(h)]
c = [[abs(a[i][j] - b[i][j]) for j in range(w)] for i in range(h)]

CONST = 80 * 80 * 2
dp = [[0] * w for _ in range(h)]
dp[0][0] = 1 << (c[0][0] + CONST)

for i in range(h):
    for j in range(w):
        if i < h - 1:
            dp[i + 1][j] |= (dp[i][j] << c[i + 1][j])
            dp[i + 1][j] |= (dp[i][j] >> c[i + 1][j])
        if j < w - 1:
            dp[i][j + 1] |= (dp[i][j] << c[i][j + 1])
            dp[i][j + 1] |= (dp[i][j] >> c[i][j + 1])

for k in range(CONST):
    if dp[h - 1][w - 1] & (1 << (CONST + k)) != 0 or dp[h - 1][w - 1] & (
            1 << (CONST - k)) != 0:
        ans = k
        break

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

x = int(input())
cnt = 0
y = x
while 1:  
  for i in range(1,y+1):
    if y % i == 0:
      cnt += 1
  if cnt == 2:
    print(y)
    break
  else:
    y += 1


      
  

### FIXED CODE ###

x = int(input())
done = True
while done :
    for i in range(2,x):
        if x % i == 0:
            x += 1
            break
    else:
        print(x)
        done = False
### BUGGY CODE ###

n,m = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(n)]
a.sort(key=lambda x:(x[0],x[1]))
c = 0
ans = 0
for i in range(n):
    for j in range(a[i][1]):
        if c < m:
            c += 1
            ans += a[i][0]
print(ans)

### FIXED CODE ###

n,m = map(int,input().split())
a = [list(map(int, input().split())) for _ in range(n)]
a.sort(key=lambda x:(x[0]))
c = 0
mony = 0
for i in a:
    if c + i[1] < m:
        c += i[1]
        mony += i[0]*i[1]
    else:
        for j in range(i[1]):
            c += 1
            mony += i[0]
            if c >= m:
                break
        break
print(mony)
### BUGGY CODE ###

from math import floor, sqrt
from collections import defaultdict
def pow(x, n, mod):
    ret = 1
    while n > 0:
        if n % 2 == 1:
            ret = ret * x % mod
        x = x * x % mod
        n >>= 1
    return ret

def factors(n):
    d = defaultdict(int)
    for i in range(2,floor(sqrt(n))+1):
        while n % i == 0:
            n //= i
            d[i] += 1
        if n == 1:
            break
    if n != 1:
        d[n] += 1
    return d

mod = 10**9+7
def gcd(x,y):
    a,b = max(x,y),min(x,y)
    r = a % b
    while r != 0:
        a,b = b,r
        r = a % b
    return b
N = int(input())
a = list(map(int,input().split()))
g = a[0]
fs = [None]*N
fs[0] = factors(a[0])
fac = factors(a[0])
for i in range(1,N):
    fs[i] = factors(a[i])
    for k in fs[i]:
        fac[k] = max(fac[k], fs[i][k])
ans = 0
for i in range(N):
    tmp = 1
    for k in fac:
        tmp *= pow(k, fac[k]-fs[i][k], mod)
    ans = (ans+tmp)%mod
print(ans%mod)

### FIXED CODE ###

def pow(x, n, mod):
    ret = 1
    while n > 0:
        if n % 2 == 1:
            ret = ret * x % mod
        x = x * x % mod
        n >>= 1
    return ret
def gcd(x,y):
    a,b = max(x,y),min(x,y)
    r = a % b
    while r != 0:
        a,b = b,r
        r = a % b
    return b
mod = 10**9+7
N = int(input())
a = list(map(int,input().split()))
g = a[0]
l = g
for i in range(1,N):
    g = gcd(l, a[i])
    l = (l*a[i])//g
ans = 0
l %= mod
for i in range(N):
    tmp = (pow(a[i], mod-2, mod)*l)%mod
    ans = (ans+tmp)%mod
print(ans%mod)