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

from collections import deque

h, w = map(int, input().split())
s = [list(map(str, input().rstrip())) for _ in range(h)]


moves = ((1, 0), (-1, 0), (0, 1), (0, -1))

ans = 0

for i in range(h):
    for j in range(w):
        if s[i][j] == "#":
            grid = [[0] * w for _ in range(h)]
            q = deque([(i, j)])
            grid[i][j] = 1
            while q:
                curr = q.popleft()
                cx, cy = curr[0], curr[1]
                for (mx, my) in moves:
                    if 0 <= cx + mx < h and 0 <= cy + my < w and grid[cx + mx][cy + my] == 0:
                        if s[cx][cy] != s[cx + mx][cy + my]:
                            q.append((cx + mx, cy + my))
                            if s[cx + mx][cy + my] == ".":
                                grid[cx + mx][cy + my] = 2
            grid = sum(grid, [])
            ans += grid.count(2)
            continue

print(ans)

### FIXED CODE ###

from collections import deque

h, w = map(int, input().split())
grid = [input() for _ in range(h)]
visited = [[0]*w for _ in range(h)]
moves = ((1, 0), (-1, 0), (0, 1), (0, -1))

ans = 0
for i in range(h):
    for j in range(w):
        if not visited[i][j]:
            bcnt, wcnt = 0, 0
            q = deque([(i, j)])
            while q:
                cx, cy = q.popleft()
                if visited[cx][cy]:
                    continue
                if grid[cx][cy] == "#":
                    bcnt += 1
                else:
                    wcnt += 1
                visited[cx][cy] = 1
                for (dx, dy) in moves:
                    if 0 <= cx + dx < h and 0 <= cy + dy < w and not visited[cx + dx][cy + dy] and grid[cx + dx][cy + dy] != grid[cx][cy]:
                        q.append((cx + dx, cy + dy))
            ans += bcnt * wcnt
print(ans)
### BUGGY CODE ###

n = int(input())
k=0
while n>0:
    k+=n%10
    n//=10
if k%9==0:
    print("Yes")
else:
    print('No')

### FIXED CODE ###

n = input()
k=0
for i in n:
    k+=int(i)
    k%=9

if k%9==0:
    print("Yes")
else:
    print('No')
### BUGGY CODE ###

# AGC 002: A – Range Product
a, b = [int(s) for s in input().split()]
c = [k for k in range(a, b + 1)]

if 0 in c:
    print('Zero')
elif len([k for k in c if k < 0]) % 2 == 0:
    print('Positive')
else:
    print('Negative')

### FIXED CODE ###

# AGC 002: A – Range Product
a, b = [int(s) for s in input().split()]

if a > 0:
    print('Positive')
elif b < 0:
    if (b - a + 1) % 2 == 0:
        print('Positive')
    else:
        print('Negative')
elif a <= 0 <= b:
    print('Zero')
### BUGGY CODE ###

N = int(input())
N = list(str(N))
N = tuple((map(int, N)))

ans = 0
flag = False
flag5 = False
for i in range(len(N)-1, -1, -1):
    x = N[i]
    if flag or (flag5 and x >= 5):
        x += 1
    flag5 = False
    flag = False
    if x > 5:
        ans += (10 - x)
        flag = True
        if i == 0:
            ans += 1
    else:
        ans += x
    if x == 5:
        flag5 = True
print(ans)

### FIXED CODE ###

N = tuple(input())
N = tuple(map(int, N))

ans = 0
flag = False
flag5 = False
i = len(N)-1


for x in reversed(N):
    if flag or (flag5 and x >= 5):
        x += 1
    flag5 = False
    flag = False
    if x > 5:
        ans += (10 - x)
        flag = True
        if i == 0:
            ans += 1
    else:

        ans += x
    if x == 5:
        flag5 = True
    i -= 1

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

### ----------------
### ここから
### ----------------

import sys
from io import StringIO
import unittest

def resolve():
    readline=sys.stdin.readline
    mod=10**9+7
    n=int(readline())
    arr=list(map(int, readline().rstrip().split()))
    binArr = [[False for i in range(60)] for j in range(n)]
    cnt=[0]*60
    for i in range(n):
        b = bin(arr[i])
        lenb = len(b)
        for j in range(2,lenb):
            if int(b[lenb+1-j])==1:
                binArr[i][j-2] = True
                cnt[j-2]+=1
    ans=[0]*60
    answer = 0
    for i in range(n):
        for j in range(60):
            # 1: cnt[j]
            # 0: n-cnt[j]
            cnt[j]-=binArr[i][j]
            if binArr[i][j] == False:
                ans[j] += cnt[j]
            else:
                ans[j] += (n-cnt[j]-i-1)
    x=1
    for i in range(60):
        answer += ans[i]*x
        answer %= mod
        x*=2
        x%=mod
    print(answer)
    return

if 'doTest' not in globals():
    resolve()
    sys.exit()

### ----------------
### ここまで 
### ----------------

### FIXED CODE ###

### ----------------
### ここから
### ----------------

import sys
from io import StringIO
import unittest

def resolve():
    readline=sys.stdin.readline
    mod=10**9+7
    n=int(readline())
    arr=list(map(int, readline().rstrip().split()))
    binArr = [[0 for i in range(60)] for j in range(n)]
    cnt=[0]*60
    for i in range(n):
        b = bin(arr[i])[2:]
        lenb = len(b)
        for j in range(lenb):
            binArr[i][j] = int(b[lenb-1-j])
            cnt[j]+=binArr[i][j]
    ans=[0]*60
    answer = 0
    for i in range(n):
        for j in range(60):
            # 1: cnt[j]
            # 0: n-cnt[j]
            cnt[j]-=binArr[i][j]
            if binArr[i][j] == 0:
                ans[j] += cnt[j]
            else:
                ans[j] += (n-cnt[j]-i-1)
    x=1
    for i in range(60):
        answer += ans[i]*x
        answer %= mod
        x*=2
        x%=mod
    print(answer)
    return

if 'doTest' not in globals():
    resolve()
    sys.exit()

### ----------------
### ここまで 
### ----------------
### BUGGY CODE ###

N = int(input())

A = [int(x) for x in input().split()]
B = [int(x) for x in input().split()]

dp = [[N] * (N + 1) for _ in range(4)]
for i in range(3):
    for w in range(N+1):
        if w >= A[i]:
            dp[i+1][w] = max(dp[i][w], dp[i+1][w-A[i]] + B[i]-A[i])
        else:
            dp[i+1][w] = dp[i][w]

M = max(dp[-1])

dp = [[M] * (M + 1) for _ in range(4)]
for i in range(3):
    for w in range(M+1):
        if w >= B[i]:
            dp[i+1][w] = max(dp[i][w], dp[i+1][w-B[i]] + A[i]-B[i])
        else:
            dp[i+1][w] = dp[i][w]
print(max(dp[-1]))


### FIXED CODE ###

import sys
if sys.version[0] == '2':
    range, input = xrange, raw_input
N = int(input())

A = [int(x) for x in input().split()]
B = [int(x) for x in input().split()]

dp = [0] * (N+1)
for a, b in ((a, b) for a, b in zip(A, B) if a < b):
    for w in range(a, N+1):
        dp[w] = max(dp[w], dp[w-a] + b-a)

M = max(dp) + N
dp = [0] * (M+1)
for a, b in ((a, b) for a, b in zip(A, B) if a > b):
    for w in range(b, M+1):
        dp[w] = max(dp[w], dp[w-b] + a-b)

print(max(dp) + M)
### BUGGY CODE ###

from heapq import heappush, heappop
import sys
input = sys.stdin.readline

h, w, k = map(int, input().split())
x1, y1, x2, y2 = map(int, input().split())
x1 -= 1
y1 -= 1
x2 -= 1
y2 -= 1
c = [list(input()) for _ in range(h)]
# print(x1, y1)
# print(x2, y2)

dx = [+1, 0, -1, 0]
dy = [0, +1, 0, -1]
MAX = 10**7
dp = [[[(MAX, MAX)] * 4 for _ in range(w)] for _ in range(h)]

q = [((1, 0, x1, y1, i)) for i in range(4)]

while q:
    c1, c2, x, y, d = q.pop()
    # print(x, y, d, c1, c2)
    if c1 > dp[x][y][d][0]:
        continue
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if nx < 0 or nx >= h or ny < 0 or ny >= w:
            continue
        if c[nx][ny] == '@':
            continue
        if i == d and c2 < k:
            if dp[nx][ny][i] > (c1, c2 + 1):
                dp[nx][ny][i] = (c1, c2 + 1)
                q.append((c1, c2 + 1, nx, ny, i))
        else:
            if dp[nx][ny][i] > (c1 + 1, 1):
                dp[nx][ny][i] = (c1 + 1, 1)
                q.append((c1 + 1, 1, nx, ny, i))

ans = min(dp[x2][y2][i][0] for i in range(4))
if ans == MAX:
    ans = -1
print(ans)


### FIXED CODE ###

from heapq import heappush, heappop
import sys
input = sys.stdin.readline

h, w, k = map(int, input().split())
x1, y1, x2, y2 = map(int, input().split())
x1 -= 1
y1 -= 1
x2 -= 1
y2 -= 1
c_ = [tuple(input()) for _ in range(h)]
c = [[False] * w for _ in range(h)]
for i in range(h):
    for j in range(w):
        if c_[i][j] == '@':
            c[i][j] = True
# print(x1, y1)
# print(x2, y2)

dx = [+1, 0, -1, 0]
dy = [0, +1, 0, -1]
MAX = 10**7


def convert(x, y, d):
    return (x * w + y) * 4 + d


# dp = [[[(MAX, MAX)] * 4 for _ in range(w)] for _ in range(h)]
dp = [MAX * (k + 1) + k] * (h * w * 4)

# q = [((1, 0, x1, y1, i)) for i in range(4)]
q = [((k + 1, convert(x1, y1, i))) for i in range(4)]

while q:
    c0, xyd = heappop(q)
    c1 = c0 // (k + 1)
    c2 = c0 % (k + 1)
    # print(x, y, d, c1, c2)
    d = xyd % 4
    y = (xyd // 4) % w
    x = (xyd // 4) // w
    if c1 > dp[xyd] // (k + 1):
        continue
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        nxyi = convert(nx, ny, i)
        if nx < 0 or nx >= h or ny < 0 or ny >= w:
            continue
        if c[nx][ny]:
            continue
        if i == d and c2 < k:
            if dp[nxyi] > c1 * (k + 1) + c2 + 1:
                dp[nxyi] = c1 * (k + 1) + c2 + 1
                heappush(q, (dp[nxyi], nxyi))
        else:
            if dp[nxyi] > (c1 + 1) * (k + 1) + 1:
                dp[nxyi] = (c1 + 1) * (k + 1) + 1
                heappush(q, (dp[nxyi], nxyi))

ans = min(dp[convert(x2, y2, i)] // (k + 1) for i in range(4))
if ans == MAX:
    ans = -1
print(ans)
### BUGGY CODE ###

def euclid(a, b):
    mod = a % b
    if mod != 0:
        b = euclid(b, mod)
    return b
N = int(input())
A = [int(a) for a in input().split()]
gcd_lis = []
for i in range(N):
    X = A[:i]+A[i+1:]
    gcd = X[0]
    for x in X:
        gcd = euclid(gcd, x)
    gcd_lis.append(gcd)
maximam = 1
for j in gcd_lis:
    maximam = max(maximam, j)
print(maximam)

### FIXED CODE ###

def euclid(a, b):
    mod = a % b
    if mod != 0:
        b = euclid(b, mod)
    return b
N = int(input())
A = [int(a) for a in input().split()]
gcd_lis = [A[0]]
gcd = A[0]
for a in A[1:]:
    gcd = euclid(gcd, a)
    gcd_lis.append(gcd)
inv_gcd_lis = [A[-1]]
gcd = A[-1]
for a in A[::-1][1:]:
    gcd = euclid(gcd, a)
    inv_gcd_lis.append(gcd)
inv_gcd_lis = inv_gcd_lis[::-1]
maximam = 0
for index in range(N):
    if index == 0:
        gcd = inv_gcd_lis[1]
    elif index == N - 1:
        gcd = gcd_lis[N-2]
    else:
        gcd = euclid(gcd_lis[index - 1], inv_gcd_lis[index + 1])
    maximam = max(gcd, maximam)
print(maximam)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
N = int(input())
A = [[0] * (N-1)]+[list(map(int,input().split())) for _ in range(N)]

idx = [0] * (N+1)
cnt = 0
day = 0
flag_max = [False] * (N+1)
while cnt != N:
    
    error = True
    lst = []
    flag =[True] * (N+1)
    for i in range(1,N+1):
        if flag_max[i]:continue
        if not(flag[i]):continue
        tmp = A[i][idx[i]]
        if not(flag[tmp]):continue
    
        if A[tmp][idx[tmp]] == i:
            lst.append(i)
            idx[tmp] = idx[tmp] + 1
            idx[i] = idx[i] + 1
            if idx[tmp] == N-1:
                cnt += 1
                flag_max[tmp] = True
            if idx[i] == N-1:
                cnt += 1
                flag_max[i] = True
            flag[i] = False
            flag[tmp] = False
            error = False
    if error:
        print(-1)
        sys.exit()
    
    day += 1
            
    
    
print(day)
    
    


### FIXED CODE ###

import sys
input = sys.stdin.readline
N = int(input())
A = [[0] * (N-1)]+[list(map(int,input().split())) for _ in range(N)]

idx = [0] * (N+1)
cnt = 0
day = 0
flag_max = [False] * (N+1)
while cnt != N:
    
    error = True
    flag =[False] * (N+1)
    looplist = [i for i in range(1,N+1) if not(flag_max[i])]
    
    for i in looplist:
        if (flag[i]):continue
        tmp = A[i][idx[i]]
        if (flag[tmp]):continue
    
        if A[tmp][idx[tmp]] == i:
            idx[tmp] = idx[tmp] + 1
            idx[i] = idx[i] + 1
            if idx[tmp] == N-1:
                flag_max[tmp] = True
                cnt += 1
            if idx[i] == N-1:
                flag_max[i] = True
                cnt += 1
            flag[i] = True
            flag[tmp] = True
            error = False
    if error:
        print(-1)
        sys.exit()
    
    day += 1
            

    if day > 10000:
        print(N*(N-1)//2)
        sys.exit()
    
    
print(day)
### BUGGY CODE ###

N, Q = map(int,input().split())
graph = {i:[] for i in range(N)}
G = {i:[] for i in range(N)}
ans = [0 for i in range(N)]
c = [0 for i in range(N)]
for i in range(N-1):
  a, b = map(int, input().split())
  graph[a-1] += [b-1]
  graph[b-1] += [a-1]
stuck = [0]
log = [0 for i in range(N)]
log[0]=1
ls = [0]
while stuck:
  x = stuck.pop()
  A = graph[x]
  flag = True
  ki = []
  for a in A:
    if log[a]==0:
      stuck+=[a]
      ki+=[a]
      log[a]=1
      flag = False
  for l in ls:
    G[l] += ki
  ls += ki
  if flag:
    ls.remove(x)
for i in range(Q):
  p, x = map(int,input().split())
  p = p-1
  c[p]+=x

for k in G.keys():
  for x in G[k]:
    ans[x]+=c[k]
  ans[k]+=c[k]
A = map(str,ans)
print(' '.join(A))

### FIXED CODE ###

from collections import deque
N, Q = map(int, input().split())
G = [[] for _ in range(N)]
count = [0]*N
for i in range(N-1):
    a, b = map(int, input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)
for i in range(Q):
    p, x = map(int, input().split())
    count[p-1]+=x
q = deque([0])
flag = [False]*N
while q:
    v = q.pop()
    flag[v] = True
    for e in G[v]:
        if flag[e]:
            continue
        count[e]+=count[v]
        q.append(e)
print(*count)
### BUGGY CODE ###

def solve():
    H,W=list(map(int,input().split(' ')))
    darker =[]
    cnt = 0
    for i in range(H):
        darker.append(list(input()))
    for i in range(H):
        darker[i].insert(0,'.')
        darker[i].append('.')
    darker.insert(0,['.' for i in range(W+2)])
    darker.append(['.' for i in range(W+2)])
    while True:
        tmp=[]
        for i in range(1,H+1):
            for j in range(1,W+1):
                if darker[i][j] =='.':
                    if darker[i-1][j] =="#" or darker[i][j-1] =="#" or darker[i+1][j] =='#' or darker[i][j+1] =='#':
                        tmp.append([i,j])
        if len(tmp) ==0:
            break
        for i in range(0,H+2):
            for j in range(0,W+2):
                if [i,j] in tmp:
                    darker[i][j]='#'

        cnt +=1
    return cnt

print(solve())

### FIXED CODE ###

import numpy as np

def solve():
    H,W=map(int,input().split(' '))
    max_value = H+W
    values =[]
    for i in range(H):
      values.append([0 if i == '#' else max_value for i in list(input())])
    values = np.array(values)

    for x in range(W-1):
        values[:,x+1] = np.minimum(values[:,x]+1,values[:,x+1])
    for x in range(W-1,0,-1):
        values[:,x-1] = np.minimum(values[:,x-1],values[:,x]+1)
    for x in range(H-1):
        values[x+1,:] = np.minimum(values[x,:]+1,values[x+1,:])
    print('')
    for x in range(H-1,0,-1):
        values[x-1,:] = np.minimum(values[x,:]+1,values[x-1,:])
    print(np.max(values))
solve()
### BUGGY CODE ###

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

ans = 1
for i in range(N):
    ans *= A[i]
    if ans == 0: break

if ans > 10**18:
    ans = -1

print(ans)


### FIXED CODE ###

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

if 0 in A:
    ans = 0
else:
    ans = 1
    for i in A:
        ans *= i
        if ans > 10**18:
            ans = -1
            break

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

import heapq
from collections import defaultdict


class Dijkstra(object):

    """ 使用例
    dik = Dijkstra()
    edge = defaultdict(list)
    edge[(1, 1)].append([1, (1, 2)])
    edge[(1, 2)].append([1, (1, 1)])
    edge[(1, 2)].append([2, (2, 1)])
    edge[(2, 1)].append([2, (1, 2)])
    edge[(2, 1)].append([5, (2, 2)])
    edge[(2, 2)].append([5, (2, 1)])
    edge[(2, 2)].append([3, (1, 2)])
    edge[(1, 2)].append([3, (2, 2)])

    s0 = (1, 1)
    ans = dik(s0, edge)

    """

    def __init(self):
        pass

    def __call__(self, s0, edge):

        # s0:始点 (,,,)
        # edge[(,,,)] = [コスト、(,,,)], [コスト、(,,,)]

        d = dict()
        used = dict()

        edgelist = edge[s0]
        heapq.heapify(edgelist)

        d[s0] = 0
        used[s0] = False

        while len(edgelist):
            minedge = heapq.heappop(edgelist)
            if not used.get(minedge[1], True):
                continue
            v = minedge[1]
            d[v] = minedge[0]
            used[v] = False

            for e in edge[v]:
                if used.get(e[1], True):
                    if d.get(e[1], float('inf')) <= d[v] + e[0]:
                        continue
                    heapq.heappush(edgelist, [d[v] + e[0], e[1]])

        return d


N, M, S = map(int, input().split())

s_max = 2500
S = min(S, s_max)

dik = Dijkstra()
edge = defaultdict(list)
s0 = (1, S)

for m in range(1, M + 1):
    U, V, A, B = map(int, input().split())
    for s in range(A, s_max + 1):
        edge[(U, s)].append([B, (V, s - A)])
        edge[(V, s)].append([B, (U, s - A)])

for n in range(1, N + 1):
    C, D = map(int, input().split())
    for s in range(s_max + 1):
        s1 = min(s + C, s_max)
        edge[(n, s)].append([D, (n, s1)])

d = dik(s0, dict(edge))

for n in range(2, N + 1):
    ans = []
    for s in range(s_max + 1):
        ans.append(d[(n, s)])
    print(min(ans))


### FIXED CODE ###

import heapq
import sys
input = sys.stdin.readline
 
INF = 10 ** 18
 
class Edge():
    def __init__(self, end, cost, time):
        self.end = end
        self.cost = cost
        self.time = time
 
dp = []
h = []
 
def push(t, v, x):
    if x < 0:
        return
    if dp[v][x] <= t:
        return
    dp[v][x] = t
    heapq.heappush(h, (t, v, x))
 
def dijkstra(n, G, cd, start, s, max_s):
    global dp
    dp = [[INF for j in range(max_s+1)] for i in range(n)] 
    push(0, start, s)
 
    while h:
        # 使っていない頂点のうち、現時点で最も到達短時間が短いものを選びvとする
        t, v, x = heapq.heappop(h)
        if dp[v][x] < t:
            continue
        # 両替
        if x < max_s:
            push(t+cd[v][1], v, min(x+cd[v][0], max_s))
        # vから到達可能な頂点について、到達時間が短くなれば更新
        for e in G[v]:
            push(t+e.time, e.end, x-e.cost)
 
 
n, m, s = map(int, input().split())
uvab = [list(map(int, input().split())) for _ in range(m)]
cd = [list(map(int, input().split())) for _ in range(n)]
 
es = [[] for i in range(n)]
max_s = 50 * (n-1)
 
for u, v, a, b in uvab:
    es[u-1].append(Edge(v-1,a,b))
    es[v-1].append(Edge(u-1,a,b))
 
dijkstra(n, es, cd, 0, min(max_s,s), max_s)
 
for i in range(1, n):
    print(min(dp[i]))
### BUGGY CODE ###

import numpy as np
n = int(input())
a = list(map(int, input().split()))
c = 0
sum = a[0]
for i in range (1, n):
    while np.sign(sum + a[i]) == np.sign(sum) or sum + a[i] == 0:
        c += 1
        if sum > 0:
            a[i] -= 1
        else:
            a[i] += 1
    sum += a[i]
print(c)

### FIXED CODE ###

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

c1 = 0
sum = 0
for i in range(n):
    sum += a[i]
    if i % 2 == 1:
        if sum <= 0:
            c1 += 1 - sum
            sum = 1
    else:
        if sum >= 0:
            c1 += 1 + sum
            sum = -1

c2 = 0
sum = 0
for i in range(n):
    sum += a[i]
    if i % 2 == 1:
        if sum >= 0:
            c2 += 1 + sum
            sum = -1
    else:
        if sum <= 0:
            c2 += 1 - sum
            sum = 1

print(min(c1, c2))
### BUGGY CODE ###

N = int(input())

def f(n):
    print(n, flush = True)
    S = input()
    if S == 'Vacant':
        exit()
    return S

l = 0
r = N - 1
S = f(l)
U = f(r)
for i in range(20):
    mid = (l + r) // 2
    U = f(mid)
    len = m - l + 1
    if ((len % 2) ^ (S == U)):
        r = mid
        S = U
    else:
        l = mid


### FIXED CODE ###

N = int(input())

def f(n):
    print(n, flush = True)
    S = input()
    if S == 'Vacant':
        exit()
    return S

l = 0
r = N
S = f(l)
for i in range(20):
    mid = (l + r) // 2
    U = f(mid)
    len = mid - l + 1
    if (len % 2 == 0 and S != U) or (len % 2 and S == U):
        l = mid
        S = U
    else:
        r = mid
### BUGGY CODE ###

a, b = map(int, input().split())
divisor = []
upper = min(a, b)//2+1
if a%2 or b%2:
    for i in range(3, upper, 2):
        divable = False
        if a % i == 0 and b % i == 0:
            for j in range(len(divisor)):
                if i % divisor[j] == 0:
                    divable = True
                    break
            if not divable:
                divisor.append(i)
else:
    two_break = False
    for i in range(2, upper):
        divable = False
        if a % i == 0 and b % i == 0:
            if i % 2 == 0 and two_break:
                continue
            for j in range(len(divisor)):
                if i % divisor[j] == 0:
                    divable = True
                    break
            if not divable:
                divisor.append(i)
                if i == 2:
                    two_break = True
print(len(divisor)+1)

### FIXED CODE ###

a, b = map(int, input().split())
def gcd(x, y):
    if y == 0:
        return x
    else:
        return gcd(y, x%y)
n = gcd(a, b)
ndiv = n
if n == 1:
    print(1)
else:
    i = 1
    primecount = 0
    divisor = False
    while True:
        i += 1
        while ndiv%i == 0:
            ndiv = ndiv//i
            divisor = True
        if divisor:
            primecount += 1
            divisor = False
            if ndiv == 1:
                break
        if ndiv != 1 and i*i > n:
            primecount += 1
            break
    print(primecount+1)
### BUGGY CODE ###

import bisect
import sys
input=sys.stdin.readline
k=int(input())
l=list(map(int,input().split()))
l.sort()
ans=0
i=0
n=k
while i<n:
    s=l[-1]
    b=1
    while b<=s:
        b*=2
    g=b-s
    p=bisect.bisect_left(l,g)
    if p==len(l)-1:
        l.pop(-1)
        i+=1
        continue
    else:
        if l[p]==g:
            l.pop(-1)
            l.pop(p)
            i+=2
            ans+=1
        else:
            l.pop(-1)
            i+=1
print(ans)


### FIXED CODE ###

from bisect import bisect_left
N=int(input())
A=list(map(int,input().split()))
B=[0]*N
A.sort()
t=0
for i in range(N):
    while 2**t<=A[i]:
        if 2**t<=A[i]<2**(t+1):
            break
        t+=1
    B[i]=2**(t+1)-A[i]
i=N-1
count=0
flag=[0]*N
for i in range(N-1,0,-1):
    if flag[i]==1:
        continue
    flag[i]=1
    b=bisect_left(A,B[i])
    if A[b]==B[i] and flag[b]==0:
        flag[i]=1
        flag[b]=1
        A[b]-=1
        count+=1
print(count)
### BUGGY CODE ###

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

def factorizationC(n,p):
    numList=[]
    for i in range(2, int(p**(1/n))+1):
        if p % (i**n) == 0:
            numList.append(i)
            m = p // (i**n)
            j = 2
            while j <= m:
                if m % (j**n) == 0:
                    numList.append(j)
                    m = m // (j**n)
                    j = 2
                else:
                    j += 1
            break
    return numList

if n==1:
  print(p)
else:
  aaa=factorizationC(n,p)
  ans=1
  for i in range(len(aaa)):
     ans=ans*aaa[i]
  print(ans)

### FIXED CODE ###

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

def factorize(n):
    fct = []  # prime factor
    b, e = 2, 0  # base, exponent
    while b * b <= n:
        while n % b == 0:
            n = n // b
            e = e + 1
        if e > 0:
            fct.append((b, e))
        b, e = b + 1, 0
    if n > 1:
        fct.append((n, 1))
    return fct

kekka=factorize(p)

ans=1
for i in range(len(kekka)):
    ans=ans* kekka[i][0] ** (kekka[i][1]//n)
print(ans)