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

import fractions
n,m = list(map(int,input().split()))
a = list(map(int,input().split()))
cnt = 0
lcm = 1
for i in range(n):
    a[i]//=2
    lcm = lcm*a[i]//fractions.gcd(lcm,a[i])
c = [0]*n
flag = False
for i in range(n):
    while a[i]%2==0:
        a[i]//=2
        c[i]+=1
    for j in range(i):
        if c[i]!=c[j]:
            flag = True
            break
    if flag:
        break
if flag:
    print(0)
else:
    tmp = m//lcm
    print((tmp+1)//2)

### FIXED CODE ###

import fractions #math.gcdは非対応なので解答にはfractions.gcdを使う
n,m = list(map(int,input().split()))
a = list(map(int,input().split()))
lcm = 1
for i in range(n):
    a[i]//=2
    lcm = lcm*a[i]//fractions.gcd(lcm,a[i])
flag = False
loopf = True
while loopf:
    tmp = a[0]%2
    for i in range(1,n):
        if a[i]%2!=tmp:
            flag = True
            loopf = False
            break
    if tmp==1 and loopf:
        loopf = False
    if tmp==0:
        for i in range(n):
            a[i]//=2
        
if flag:
    print(0)
else:
    tmp = m//lcm
    print((tmp+1)//2)
### BUGGY CODE ###

def gcd(a,b):
	if a==0:
		return(b)
	return(gcd(b%a,a))
a,b=map(int,input().split())
g=gcd(a,b)

divide=2
ans=1
while(g!=1 and g>=divide):
	if g%divide==0:
		ans+=1
		while(g%divide==0):
			g//=divide
	divide+=1
print(ans)

### FIXED CODE ###

from math import sqrt
def gcd(a,b):
	if a==0:
		return(b)
	return(gcd(b%a,a))
a,b=map(int,input().split())
g=gcd(a,b)
ans=1
if g%2==0:
	ans+=1
	while(g%2==0):
		g//=2
for divide in range(3,int(sqrt(g))+1,2):
	if g%divide==0:
		ans+=1
		while(g%divide==0):
			g//=divide
if g>2:
	ans+=1
print(ans)
### BUGGY CODE ###

n=int(input())
power=1
for i in range(1, n+1):
    power *=i
answer=power%(10**9+7)
print(answer)


### FIXED CODE ###

n=int(input())
power=1
for i in range(1, n+1):
    power = power*i%(10**9+7)
print(power)
### BUGGY CODE ###

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

ans = 10**10

for i in range(1,n):
    s = abs(sum(a_li[:i]) - sum(a_li[i:]))
    ans = min(ans,s)
    
print(ans)

### FIXED CODE ###

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

ans = 10**10
s = sum(a_li)
tmp = 0

for i in range(n):
    tmp += a_li[i]
    res = abs(s - 2*tmp)
    ans = min(ans,res)
    
print(ans)
### BUGGY CODE ###

n=int(input())
a=[int(i) for i in input().split()]
ans=0
for i in range(64):
    x,y=0,0
    for j in a:
        if j>>i&1:
            y+=1
        else:
            x+=1
    ans+=x*y*(1<<i)
    ans%=10**9+7
print(ans)


### FIXED CODE ###

n=int(input())
a=[int(i) for i in input().split()]
ans=0
for i in range(64):
    x,y=0,0
    for j in a:
        if j>>i&1:
            y+=1
        else:
            x+=1
    ans+=x*y*(1<<i)
    ans%=10**9+7
print(ans)
### BUGGY CODE ###

import functools
import fractions

def main():
  if 'get_ipython' not in globals():  
    # For Subsession
    N = int(input())
    A = list(map(int, input().split()))
  else:
    # N = 3
    # A = [7,6,8]
    # N = 3
    # A = [12,15,18]
    N = 3
    A = [1,1000000000,1000000000]

  AL = [0] * N    
  AR = [0] * N
  for i in range(N):
    if i != 0:
      AL[i] = functools.reduce(fractions.gcd, A[0:i+1])
    else:
      AL[i] = A[i]
    if i != N - 1:
      AR[i] = functools.reduce(fractions.gcd, A[i:])
    else:
      AR[i] = A[i]
      
  # print(AL)
  # print(AR)
  x = 0
  for i in range(N):
    if i == 0:
      tmp = AR[i+1]
    elif i == N - 1:
      tmp = AL[i-1]
    else:
      tmp = fractions.gcd(AL[i-1],AR[i+1])
    # print(tmp)
    if tmp > x: x = tmp
  
  print(x)
    
main()

### FIXED CODE ###

import functools
import fractions

def main():
  if 'get_ipython' not in globals():  
    # For Subsession
    N = int(input())
    A = list(map(int, input().split()))
  else:
    # N = 3
    # A = [7,6,8]
    N = 3
    A = [12,15,18]
    # N = 3
    # A = [1,1000000000,1000000000]

  AL = [0] * N    
  AR = [0] * N
  for i in range(N):
    if i != 0:
      AL[i] = fractions.gcd(AL[i-1],A[i])
    else:
      AL[i] = A[i]
    j = N - i - 1
    if j!= N - 1:
      AR[j] = fractions.gcd(AR[j+1],A[j])
    else:
      AR[j] = A[j]
      
  if 'get_ipython' in globals():   
    print(AL)
    print(AR)
  
  x = 0
  for i in range(N):
    if i == 0:
      tmp = AR[i+1]
    elif i == N - 1:
      tmp = AL[i-1]
    else:
      tmp = fractions.gcd(AL[i-1],AR[i+1])
    if tmp > x: x = tmp
  
  print(x)
    
main()
### BUGGY CODE ###

# coding: utf-8
input_lines=input().split()
K = int(input_lines[0])
S = int(input_lines[1])
M=0
for i in range(K+1):
  for j in range(i,K+1):
    for k in range(j,K+1):
      if i+j+k==S:
        if i==j==k:
          M+=1
        elif i==j or j==k:
          M+=3
        else:
          M+=6
print(M)

### FIXED CODE ###

# coding: utf-8
input_lines=input().split()
K = int(input_lines[0])
S = int(input_lines[1])
M=0
for i in range(K+1):
  for j in range(i,K+1):
    k =S-i-j
    if i<=j<=k<=K:
      if i==j==k:
        M+=1
      elif i==j or j==k:
        M+=3
      else:
        M+=6
print(M)
### BUGGY CODE ###

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

for i in range(1,1+N):
    print(A.count(str(i)))

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
D = [0 for i in range(N)]

for i in A:
    D[i-1] += 1

for i in range(len(D)):
    print(D[i])
### BUGGY CODE ###

n = int(input())
S = [int(s) for s in input().split()]

q = int(input())
T = [int(t) for t in input().split()]
 
cnt = sum(t in S for t in T)
 
print(cnt)

### FIXED CODE ###

import sys

def BinarySearch(S, n, t):
    bottom = 0
    top = n - 1

    while bottom <= top:
        center = (bottom + top) // 2

        if S[center] == t:
            return center
        elif S[center] < t:
            bottom = center + 1
        else:
            top = center - 1

    return -1


n = int(sys.stdin.readline())
S = [int(s) for s in sys.stdin.readline().split()]

q = int(sys.stdin.readline())
T = {int(t) for t in sys.stdin.readline().split()}

ans = sum(BinarySearch(S, n, t) != -1 for t in T)

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

N, M=map(int, input().split())
A=list(map(int, input().split()))
for i in range(M):
  B, C=map(int, input().split())
  A=A+[C]*B
  
A.sort()
print(int(sum(A[-N:])))

### FIXED CODE ###

from collections import defaultdict

cnt=defaultdict(int)

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

for i in range(N):
  cnt[A[i]]+=1

tmp=[0]*M
for i in range(M):
  B, C=map(int, input().split())
  cnt[C]+=B
  tmp[i]=C
A+=tmp

tmp=list(cnt.keys())
tmp.sort()
j=-1
out=0
while N>0:
  if cnt[tmp[j]]<=N:
    out+=tmp[j]*cnt[tmp[j]]
    N-=cnt[tmp[j]]
  else:
    out+=tmp[j]*N
    N=0
    
  j-=1
print(out)
### BUGGY CODE ###

import bisect

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

As.sort()

#print(As)

for _ in range(M):
    discount = As.pop(-1) // 2

    bisect.insort_left(As, discount)
#    print(As)

print(sum(As))

### FIXED CODE ###

import bisect

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

As.sort()

#print(As)

for _ in range(M):
    discount = As.pop(-1)

    if(discount == 0):
        break

    discount //= 2

    i = bisect.bisect_left(As, discount)
    As.insert(i, discount)
#    print(As)

print(sum(As))
### BUGGY CODE ###

import sys

s = input()
q = int(input())

for query in sys.stdin:
    try:
        t,f,c = query.split()
        if f == '1':
            s = c + s
        elif f == '2':
            s = s + c
    except Exception:
        s = s[::-1]
print(s)

### FIXED CODE ###

import sys
from collections import deque

# sys.stdin = open('test_cases/abc158d/in/01.txt', 'r')
# sys.stdin = open('input.txt', 'r')

s = deque([s for s in input()])
q = int(input())
rev = False

for query in sys.stdin:
    if query.strip() == '1': # sys.stdin does not remove line breaks. (vs. input() removes line breaks)
        if rev:
            rev = False
        else:
            rev = True
    else:
        t,f,c = query.split()
        if f == '1':
            if rev:
                s.append(c)
            else:
                s.appendleft(c)
        elif f == '2':
            if rev:
                s.appendleft(c)
            else:
                s.append(c)
if rev == True:
    s.reverse()
print(''.join(s))
### BUGGY CODE ###

# Ai>=Bi 出来るならそのままにする
# Ai < Bi 仕方ないので溢れたぶんを使う
# 「変更したAi」の最小値が欲しいので、使うのは余ってるやつが多い順に使ったほうがいい

n = int(input())
arr = list(map(int, input().split()))
brr = list(map(int, input().split()))

lack, lack_i = 0, []
extra, extra_i = 0, []
for i in range(n):
    if arr[i] < brr[i]:
        lack += brr[i] - arr[i]
        lack_i.append([i, brr[i] - arr[i]])
    else:
        extra += arr[i] - brr[i]
        extra_i.append([i, arr[i] - brr[i], False])

if lack > extra:
    print(-1)
    exit()

# 大量に余っているやつから優先的に使う
extra_i = list(sorted(extra_i, key=lambda x: x[1], reverse=True))
ans = 0

l_i = 0
e_i = 0

while True:
    if l_i >= len(lack_i):
        break
    e_i = 0
    while True:
        if lack_i[l_i][1] <= extra_i[e_i][1]:
            extra_i[e_i][2] = True  # 一回でも使用した
            ans += 1  #
            extra_i[e_i][1] -= lack_i[l_i][1]
            break
        else:
            extra_i[e_i][2] = True  # 一回でも使用した
            e_i += 1
            lack_i[l_i][1] -= extra_i[e_i][1]
            extra_i[e_i][1] = 0
        if e_i > len(extra_i):
            break  # ここにくるときがよくわからんけど
    l_i += 1

bonus = len(list(filter(lambda x: x[2] == True, extra_i)))
print(ans + bonus)


### FIXED CODE ###

# にぶたんが失敗したので両端からしゃくとりするような感じでやってみる
# 差分でソートして大きく足りないものは大きく余ってるやつをぶつける

N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
if sum(A) < sum(B):
    print(-1)
    exit()
D = []
pre_ans = 0  # 確実に変えなくてはいけないやつ
for i in range(N):
    if A[i] != B[i]:
        D.append(A[i] - B[i])
        if A[i] < B[i]:
            pre_ans += 1
D = sorted(D)

used = 0
tmp = 0
# print(D)
l, r = 0, len(D)
while r - l > 1:
    # print("now tmp: {}".format(tmp))
    if tmp + D[l] < 0:
        # 新たに借りる
        r -= 1
        used += 1
        tmp += D[r]
    tmp += D[l]
    l += 1
print(used + pre_ans)
### BUGGY CODE ###

def actual(K, S):
    count = 0

    for x in range(S + 1):
        for y in range(S + 1):
            z = S - (x + y)

            cond1 = (0 <= x <= K) and (0 <= y <= K) and (0 <= z <= K)
            cond2 = (x + y + z) == S

            if cond1 and cond2:
                count += 1

    return count

K, S = map(int, input().split())
print(actual(K, S))

### FIXED CODE ###

def actual(K, S):
    count = 0

    for x in range(K + 1):
        for y in range(K + 1):
            z = S - (x + y)

            cond1 = (0 <= x <= K) and (0 <= y <= K) and (0 <= z <= K)
            cond2 = (x + y + z) == S

            if cond1 and cond2:
                count += 1

    return count

K, S = map(int, input().split())
print(actual(K, S))
### BUGGY CODE ###

import sys
input = sys.stdin.readline
H,W = [int(i) for i in input().split()]
A = []
P = []
check = [[True for _ in range(W)] for _ in range(H)]

for j in range(H):
    a = list(input())
    if '#' in a:
        for i in range(W):
            if a[i] == '#':
                check[j][i] = False
                P.append([j,i])
    A.append(a)

ans = [[0 for _ in range(W)] for _ in range(H)]
count = 0
while len(P) != 0:
    hNow,wNow = P.pop(0)
    if hNow-1 >= 0:
        if check[hNow-1][wNow]:
            P.append([hNow-1,wNow])
            ans[hNow-1][wNow] = ans[hNow][wNow]+1
            check[hNow-1][wNow] = False
            count = max(count,ans[hNow-1][wNow])

    if hNow+1 < H:
        if check[hNow+1][wNow]:
            P.append([hNow+1,wNow])
            ans[hNow+1][wNow] = ans[hNow][wNow]+1
            check[hNow+1][wNow] = False
            count = max(count,ans[hNow+1][wNow])

    if wNow-1 >= 0:
        if check[hNow][wNow-1]:
            P.append([hNow,wNow-1])
            ans[hNow][wNow-1] = ans[hNow][wNow]+1
            check[hNow][wNow-1] = False
            count = max(count,ans[hNow][wNow-1])

    if wNow+1 < W:
        if check[hNow][wNow+1]:
            P.append([hNow,wNow+1])
            ans[hNow][wNow+1] = ans[hNow][wNow]+1
            check[hNow][wNow+1] = False
            count = max(count,ans[hNow][wNow+1])

print(count)


### FIXED CODE ###

from collections import deque

H,W = [int(i) for i in input().split()]
l = [list(input()) for _ in range(H)]
ans = [[-1]*W for _ in range(H)]
q = deque()

for i in range(H):
    for j in range(W):
        if l[i][j] == '#':
            q.append([i,j])
            ans[i][j] = 0

t = 0
while q:
    i,j = q.popleft()
    for next_i, next_j in [[i+1,j], [i-1,j], [i,j+1], [i,j-1]]:
        if 0 <= next_i < H and 0 <= next_j < W:
            if ans[next_i][next_j] == -1 and l[next_i][next_j] == '.':
                ans[next_i][next_j] = ans[i][j] + 1
                t = max(t, ans[next_i][next_j])
                q.append([next_i,next_j])

print(t)
### BUGGY CODE ###

A, B, C, D, E, F = map(int, input().split())

tmp = 0
ans_A = 0
ans_B = 0
for a in range(31):
    for b in range(31):
        x = 100 * (a * A + b * B)
        for c in range((x // 100 * E) // C + 1):
            for d in range((x // 100 * E) // D + 1):
                y = c * C + d * D
                if x + y > F or y > x * E // 100:
                    break
                if x + y != 0:
                    if y / (x + y) > tmp:
                        ans_A = x + y
                        ans_B = y
                        tmp = y / (x + y)

if ans_A == 0:
    print(100 * A, 0)
else:
    print(ans_A, ans_B)


### FIXED CODE ###

A, B, C, D, E, F = map(int, input().split())

tmp = 0
ans_A = 0
ans_B = 0
for a in range(31):
    for b in range(31):
        x = 100 * (a * A + b * B)
        if x > F:
            break
        for c in range((x // 100 * E) // C + 1):
            for d in range(((x // 100 * E) - c) // D + 1):
                y = c * C + d * D
                if x + y > F or y > x * E // 100:
                    break
                if x + y != 0:
                    if y / (x + y) > tmp:
                        ans_A = x + y
                        ans_B = y
                        tmp = y / (x + y)

if ans_A == 0:
    print(100 * A, 0)
else:
    print(ans_A, ans_B)
### BUGGY CODE ###

N=int(input())
S=input()
key=set()
for i in range(N):
    if i>0 and S[i-1]==S[i]:
        continue
    for j in range(i+1, N):
        if j>i+1 and S[j-1]==S[j]:
            continue
        for k in range(j+1, N):
            if k>j+1 and S[k-1]==S[k]:
                continue
            key.add(S[i]+S[j]+S[k])
print(len(key))

### FIXED CODE ###

N=int(input())
S=input()
count=0
for i in range(1000):
    p='0'*(3-len(str(i)))+str(i)
    p1=S.find(p[0])
    if p1!=-1:
        p2=S[p1+1:].find(p[1])
        if p2!=-1:
            p3=S[p1+p2+2:].find(p[2])
            if p3!=-1:
                count+=1
print(count)
### BUGGY CODE ###

n=int(input())
x,y=1,1
for _ in range(n):
  t,a=map(int,input().split())
  for i in range(x-x%t,x*1000+1,t):
    if i>=x and i//t*a>=y:break
  x,y=i,i//t*a
print(x+y)
    

### FIXED CODE ###

n=int(input())
x,y=1,1
for _ in range(n):
  t,a=map(int,input().split())
  m=max((x+t-1)//t,(y+a-1)//a)
  x,y=m*t,m*a
print(x+y)
### BUGGY CODE ###

from scipy.misc import comb
#from scipy.special import comb
import itertools

N, X, Y = map(int, input().split())

combi = list(itertools.combinations(range(1,N+1), 2))
#print(combi)
dist = {}
for i in range(1, N):
    dist[i] = 0

for kyori in combi:
    a = kyori[1] - kyori[0]
    b = int(abs((kyori[1] - Y))) + 1 + int(abs((X - kyori[0])))
    c = min([a, b])
    dist[c] += 1
    #print(c, kyori)
dist2 = sorted(dist.items())
#print(dist, dist2)
for i in range(0, N-1):
    print(dist2[i][1])


### FIXED CODE ###

import itertools

N, X, Y = map(int, input().split())

combi = list(itertools.combinations(range(1,N+1), 2))
dist = [[i+1, 0] for i in range(0, N-1)]

c = [min([kyori[1] - kyori[0], int(abs((kyori[1] - Y))) + 1 + int(abs((X - kyori[0])))]) for kyori in combi]

for i in range(len(c)):
    dist[c[i]-1][1] += 1
for i in range(0, N-1):
    print(dist[i][1])
### BUGGY CODE ###

from math import gcd
N = int(input())
A = list(map(int,input().split()))

def solve():
    g = 0
    for a in A:
        g = gcd(g,a)
    if g > 1:
        print('not coprime')
        exit()

    def factorize(n):
        d = set()
        m = 2
        while m*m <= n:
            while n%m == 0:
                n //= m
                d.add(m)
            m += 1
        if n > 1:
            d.add(n)
        return d

    st = set()
    for a in A:
        fac = factorize(a)
        if fac & st:
            print('setwise coprime')
            exit()
        st |= fac
    print('pairwise coprime')
solve()

### FIXED CODE ###

from math import gcd
N = int(input())
A = list(map(int,input().split()))

g = 0
for a in A:
    g = gcd(g,a)
if g > 1:
    print('not coprime')
    exit()

sa = set()
for a in A:
    if a==1: continue
    if a in sa:
        print('setwise coprime')
        exit()
    sa.add(a)

MAXN = 10**6+10
sieve = [0,0] + [1]*MAXN
p = 2
small_primes = []
while p*p <= MAXN:
    if sieve[p]:
        small_primes.append(p)
        for q in range(2*p,MAXN+1,p):
            sieve[q] = 0
    p += 1

st = set()
for a in A:
    for p in small_primes:
        found = False
        while a%p==0:
            a //= p
            found = True
        if found:
            if p in st:
                print('setwise coprime')
                exit()
            st.add(p)
        if a==1: break
    else:
        if a in st:
            print('setwise coprime')
            exit()
        st.add(a)

print('pairwise coprime')
### BUGGY CODE ###

from collections import deque

def main():
  h,w=map(int,input().split())
  mp=[input() for _ in range(h)]
  dist=[-1]*(h*w)
  q=deque()
  
  for i in range(h):
    for j in range(w):
      if mp[i][j]=="#":
        q.append(i*w+j)
        dist[i*w+j]=0
      else:
        dist[i*w+j]=-1
 
  while q:
    c=q.popleft()
    x=c//w
    y=c%w
    for i,j in ((1,0),(0,1),(-1,0),(0,-1)):
      xx,yy=x+i,y+j
      if (0<=xx<h and 0<=yy<w and dist[xx*w+yy]==-1):
        dist[xx*w+yy]=dist[x*w+y]+1
        q.append(xx*w+yy)

  ret=0
  for i in range(h):
    for j in range(w):
      ret=max(ret,dist[i*w+j])
      
  print(ret)
  return

main()


### FIXED CODE ###

#copipe
#1次元で格納

def main():
    h,w = map(int,input().split())
    a = []
    for i in range(h):
        a.append(input())

    used = [True]*(h*w)

    p = []
    for i in range(h):
        for j in range(w):
            if a[i][j] == '#':
                p.append(i*w+j)
                used[i*w+j] = False


    
    res = 0
    while p:
        tank = []
        for e in p:
            if e>w-1 and used[e-w]:
                tank.append(e-w)
                used[e-w] = False
            if e%w > 0 and used[e-1]:
                tank.append(e-1)
                used[e-1] = False
            if e<(h-1)*w and used[e+w]:
                tank.append(e+w)
                used[e+w] = False
            if e%w<w-1 and used[e+1]:
                tank.append(e+1)
                used[e+1] =  False
        p = tank
        res += 1
    print(res-1)

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

MOD=10**9+7
N=int(input())
A=list(map(int,input().split()))
res=0
bit=[[0]*60 for i in range(N+1)]
for i in range(1,N+1):
    for j in range(60):
        if(A[i-1]>>j&1):
            bit[i][j]=bit[i-1][j]+1
            res=(res+(2**j)*(i-bit[i][j]))%MOD
        else:
            bit[i][j]=bit[i-1][j]
            res=(res+(2**j)*bit[i][j])%MOD
print(res)

### FIXED CODE ###

MOD=10**9+7
N=int(input())
A=list(map(int,input().split()))
ans=0
for j in range(60):
    k=2**j
    count=0
    for i in range(N):
        if(A[i]&k):
            ans=(ans+(2**j)*(i-count))%MOD
            count+=1
        else:
            ans=(ans+(2**j)*count)%MOD
print(ans)
### BUGGY CODE ###

#!/usr/bin/env python3
from collections import defaultdict
n=int(input())
s=input()
count=0
mojiretu=defaultdict(tuple)
for i in range(n-1):
    for j in range(i+1,n+1):
        if mojiretu[s[i:j]]:
            if j <= mojiretu[s[i:j]][0] or mojiretu[s[i:j]][1]<=i:
                count=max(count,j-i)
        else:mojiretu[s[i:j]]=(i,j)
# while True:
#     for i in range(n)
print(count)


### FIXED CODE ###

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

class RollingHash():
    BASE1 = 1007
    BASE2 = 2009
    MOD1 = 1000000007
    MOD2 = 1000000009
 
    def __init__(self, s, opt=2):
        self.n = len(s)
        self.opt = opt
        self.hash1 = [0] * (self.n + 1)
        self.power1 = [1] * (self.n + 1)
        if opt == 2:
            self.hash2 = [0] * (self.n + 1)
            self.power2 = [1] * (self.n + 1)
        for i, e in enumerate(s):
            self.hash1[i + 1] = (self.hash1[i] * self.__class__.BASE1 + ord(e)) % self.__class__.MOD1
            self.power1[i + 1] = (self.power1[i] * self.__class__.BASE1) % self.__class__.MOD1
            if opt == 2:
                self.hash2[i + 1] = (self.hash2[i] * self.__class__.BASE2 + ord(e)) % self.__class__.MOD2
                self.power2[i + 1] = (self.power2[i] * self.__class__.BASE2) % self.__class__.MOD2
 
    def get(self, l: int, r: int):
        res1 = self.hash1[r] - self.hash1[l] * self.power1[r - l] % self.__class__.MOD1
        if(res1 < 0):
            res1 += self.__class__.MOD1
        if self.opt == 2:
            res2 = self.hash2[r] - self.hash2[l] * self.power2[r - l] % self.__class__.MOD2
            if(res2 < 0):
                res2 += self.__class__.MOD2
        return (res1, res2) if self.opt == 2 else res1


    
rh = RollingHash(S, opt=1)

def check(n: int):
    d = dict()
    for i in range(N - n + 1):
        p = rh.get(i, i + n)
        if p in d.keys():
            if(i - d[p] >= n):
                return True
        else:
            d[p] = i
    return False
    
ok, ng = 0, N // 2 + 1
while ng - ok > 1:
    mid = (ok + ng) // 2
    if check(mid):
        ok = mid
    else:
        ng = mid
print(ok)
### BUGGY CODE ###

n, p = map(int, input().split())
from collections import defaultdict
prime_list = [2]
for i in range(3, int(p ** (0.5)), 2):
    for prime in prime_list:
        if i % prime == 0:
            break
    prime_list.append(i)
pt = p
prime_dict = defaultdict(lambda : 0)
for prime in prime_list:
    point = 0
    while pt % prime == 0:
        point += 1
        pt = pt // prime
    prime_dict[prime] = point
ans = 1
if n > 1:
    for i, j in prime_dict.items():
        if j >= n:
            ans = ans * i
else:
    ans = p
print(ans)

### FIXED CODE ###

import collections

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

n, p = map(int, input().split())
t = collections.Counter(prime_return(p))
ans = 1
for k, v in t.items():
    if v >= n:
        ans *= (k ** (v // n))
print(ans)