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

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

if P == 2 or P == 5:
    ans = 0
    for i, s in enumerate(S):
        if int(s) % P == 0:
            ans += i+1
    print(ans)
    import sys
    sys.exit()

val = int(S)
order = 10 ** N
suf_nums = [-1] * N
s = -1
for i in range(N):
    if s != -1:
        val -= s * order
    suf_nums[i] = val
    s = int(S[i])
    order //= 10

surpluses = [0] * P
ans = 0
suf_nums.reverse()
for num in suf_nums:
    surplus = num % P
    surpluses[surplus] += 1
    if surplus == 0:
        ans += surpluses[0]
    else:
        ans += surpluses[surplus] - 1

print(ans)



### FIXED CODE ###

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

if P == 2 or P == 5:
    ans = 0
    for i, s in enumerate(S):
        if int(s) % P == 0:
            ans += i+1
    print(ans)
    import sys
    sys.exit(0)

surpluses = [0] * P
s = 0
power = 1
for i in range(N):
    s = (s + int(S[-1-i]) * power) % P
    surpluses[s % P] += 1
    power = (power * 10) % P

ans = surpluses[0]
for count in surpluses:
    ans += count * (count - 1) // 2

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

N = int(input())
H = [int(e) for e in input().split()]
count_max = 0
for i in range(N):
  count = 0
  for j in range(i,N-1):
    if H[j] >= H[j+1]:
      count += 1
    else:
      i += j
      break;

  if count_max < count:
    count_max = count

print(count_max)

### FIXED CODE ###

N = int(input())
H = [int(e) for e in input().split()]
count_max = 0
i = 0
while i < N:
  judge = True
  count = 0
  tmp = i
  for j in range(tmp,N):
    if j < N-1:
      if H[j] >= H[j+1]:
        count += 1
      else:
        break;

  #print(count)
  if count_max < count:
    count_max = count
  if judge == True:
    i += count + 1

print(count_max)
### BUGGY CODE ###

#!/usr/bin/env python3
import sys


def solve(s: str):

    res = 0

    s = list(s)
    for i in range(len(s)-2):
        if s[i] == "A" and s[i+1] =="B" and s[i+2] =="C":
            ai = -1
            for j in range(i-1,-1,-1):
                if j >=0 and s[j] == "A":
                    ai = j 
                else:
                    break
            if ai >= 0:
                s[ai]   = "B"
                s[ai+1] = "C"
                s[ai+2] = "A"

                res += 1
                for k in range(ai+3,i+3):
                    s[k] = "A"
                    res += 1
            else:
                s[i]   = "B"
                s[i+1] = "C"
                s[i+2] = "A"
                res += 1
    print(res)

    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    s = next(tokens)  # type: str
    solve(s)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys

def conv2num(c):
    if c == "A":
        return 1
    elif c == "D":
        return 2
    elif c == "B":
        return 3
    else:
        return 4

def solve(s: str):

    res = 0
    s = s.replace("BC","D")
    s = [ conv2num(c) for c in s ]

    acnt = 0
    for i,c in enumerate(s):
        if c == 1:
            acnt += 1
        elif c == 2:
            res += acnt
        else:
            acnt = 0


    print(res)

    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    s = next(tokens)  # type: str
    solve(s)

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

S = int(input())
x1, y1 = 0, 0
y2 = 0
x3 = 0
x2, y3 = 0, 0

for i in range(int(S ** 0.5), S + 1):
  x2 = i
  y3 = S // i
  if S % x2 == 0 and x2 <= 1000000000:
    break
print("{} {} {} {} {} {}".format(x1, y1, x2, y2, x3, y3))


### FIXED CODE ###

S = int(input())
MOD = 10 ** 9
x1, y1, x2, y2 = 0, 0, MOD, 1
y3 = S // MOD
if S % MOD != 0:
  y3 += 1
x3 = x2 * y3 - S

print("{} {} {} {} {} {}".format(x1, y1, x2, y2, x3, y3))
### BUGGY CODE ###

n, m = map(int, input().split())
p = []
y = []
d = {}
for n_ in range(n):
    d[n_ + 1] = []
for i in range(m):
    p_, y_ = map(int, input().split())
    p.append(p_)
    y.append(y_)
    d[p_].append(y_)
for i in d.keys():
    d[i] = sorted(d[i])
for i in range(m):
    print('{:06d}{:06d}'.format(p[i], d[p[i]].index(y[i]) + 1))


### FIXED CODE ###

import numpy as np
from bisect import bisect_right
# from time import time
# start = time()
n, m = map(int, input().split())
p = []
y = []
d = {i + 1: [] for i in range(n)}
# n, m = 10**5, 10**5
# p = [10**5]*m
# y = [i + 1 for i in range(m)]
for i in range(m):
    p_, y_ = map(int, input().split())
    # p_, y_ = p[i], y[i]
    p.append(p_)
    y.append(y_)
    d[p_].append(y_)
for i in d.keys():
    d[i] = sorted(d[i])
for i in range(m):
    # print('{:06d}{:06d}'.format(p[i], d[p[i]].index(y[i]) + 1))
    print('{:06d}{:06d}'.format(p[i], bisect_right(d[p[i]], y[i])))
#
# print(time() - start)
### BUGGY CODE ###

def main():

    n = int(input())
    db = []
    kinds = 0

    for i in range(10):
        tmp = []
        db.append(tmp)

    for i in range(n):
        str = input()
        num = len(str)

        if(not(str in db[num-1])):
            db[num-1].append(str)
            kinds = kinds + 1

    print(kinds)

main()


### FIXED CODE ###

def main():

    n = int(input())
    db = set()

    for i in range(n):
        db.add(input())

    print(len(db))

main()
### BUGGY CODE ###

import itertools
import fractions

N = input()
N = int(N)

l = list(itertools.combinations_with_replacement(list(range(1,N+1)), 3))
s_all = 0
for nums in l:
    count = 0
    ans = nums[0]
    for i in range(1, 3):
        ans = fractions.gcd(ans, nums[i])
    a,b,c = nums[0], nums[1], nums[2]
    if a==b:
        count+=1
    if a==c:
        count+=1
    if b==c:
        count+=1

    if count==0:
        num = 6
    elif count==1:
        num=3
    elif count==3:
        num=1
    s_all += ans*num
print(s_all)


### FIXED CODE ###

import itertools
import fractions
import functools

N = input()
N = int(N)

l = list(itertools.combinations_with_replacement(list(range(1,N+1)), 3))
s_all = 0

def euclid(a, b):
    if b == 0:
        return a
    else:
        return euclid(b, a%b)
def gcd(nums):
    return functools.reduce(euclid, nums)

for nums in l:
    count = 0
    # ans = nums[0]
    # for i in range(1, 3):
    #     ans = fractions.gcd(ans, nums[i])
    # ans = list(map(int, input().split()))
    ans = gcd(nums)
    a,b,c = nums[0], nums[1], nums[2]
    if a==b:
        count+=1
    if a==c:
        count+=1
    if b==c:
        count+=1

    if count==0:
        num = 6
    elif count==1:
        num=3
    elif count==3:
        num=1
    s_all += ans*num
print(s_all)
### BUGGY CODE ###

N,A,B = map(int,input().split())
balls = []
odd = 1
while len(balls)<=N:
    if odd == 1:
        for i in range(1,A+1):
            balls = balls + ["b"]
        odd = 0
    else:
        for i in range(1,B+1):
            balls = balls + ["r"]
        odd = 1
balls = balls[:N]
print(balls.count("b"))

### FIXED CODE ###

N,A,B = map(int,input().split())
balls = A + B
N_surplus = N%balls
if N_surplus < A:
    blues = (N//balls)*A + N_surplus
else:
    blues = (N//balls)*A + A
print(blues)
### BUGGY CODE ###

N = int(input())
txy = [list(map(int, input().split())) for _ in range(N)]

result = True

for pol in txy:
    
    if(abs(pol[1]) + abs(pol[2]) not in list(range(pol[0], -1, -2))):
        result = False

print(("No", "Yes")[result])

### FIXED CODE ###

N = int(input())
txy = [[0, 0, 0]] + [list(map(int, input().split())) for _ in range(N)]
result = True

for i in range(N):
    dt = txy[i + 1][0] - txy[i][0]
    dist = abs(txy[i + 1][1] - txy[i][1]) + abs(txy[i + 1][2] - txy[i][2])
    
    if(dist > dt): result = False
    if(dist % 2 != dt % 2): result = False

print(("No", "Yes")[result])
### BUGGY CODE ###

n = int(input())
ans = 0
for i in range(n-1):
    ans += i + 1
if n == 1:
    ans = 0
print(ans)

### FIXED CODE ###

n = int(input())
ans = 0
ans = (1 + n-1)*(n-1)//2
if n == 1:
    ans = 0
print(ans)
### BUGGY CODE ###

L, R = map(int, input().split())

mod = 2019
ans = 10 ** 7
results = [False for _ in range(2019)]
for low in range(L, R+1):
    for up in range(low+1, R+1):
        ans = min(ans, low * up % mod)
        results[low * up % mod] = True
        if all(results):
            print(ans)
            exit()
print(ans)


### FIXED CODE ###

L, R = map(int, input().split())

mod = 2019
ans = 10 ** 7
results = [False for _ in range(2019)]
for low in range(L, R+1):
    for up in range(low+1, R+1):
        ans = min(ans, low * up % mod)
        if ans == 0:
            print(ans)
            exit()
        # results[low * up % mod] = True
        # if all(results):
        #     print(ans)
        #     exit()
print(ans)
### BUGGY CODE ###

def main():
  from collections import Counter
  n,k,*a = map(int,open(0).read().split())
  a = Counter(a)
  ans = 0
  for i in range(max(0,len(a)-k)):
    ans += a.most_common()[-1-i][1]
  print(ans)
main()

### FIXED CODE ###

n,k,*a = map(int,open(0).read().split())
b = {}
for i in a:
  if i in b:
    b[i] += 1
  else:
    b[i] = 1
ans = 0
a = sorted(list(b.values()))
for i in range(max(0,len(a)-k)):
  ans += a[i]
print(ans)
### BUGGY CODE ###

N = int(input())
S = input()
ls = list(S)
count = 0
for k in range(2,N):
  for j in range(1,k):
    for i in range(0,j):
      if ls[i] != ls[j] and ls[j] != ls[k] and ls[k] != ls[i] and j - i != k - j:
        count += 1
print(count)

### FIXED CODE ###

import itertools
N = int(input())
S = input()
ls = list(S)

nr = len([r for r in S if r == 'R'])
nb = len([b for b in S if b == 'B'])
ng = len([g for g in S if g == 'G'])

ALL = nr * nb * ng
count = 0

RGBs = list(itertools.permutations(['R', 'G', 'B'], 3))

for i in range(N):
  for j in range(N-i*2):
    if (S[j], S[j+i], S[j+i*2]) in RGBs:
      count += 1
      
print(ALL - count)
### BUGGY CODE ###

N, M = map(int, input().split())
for i in reversed(range(1, M // N + 1)):
    if M % i == 0:
        print(i)
        exit(0)

### FIXED CODE ###

# ND <= M
# D <= M // N
# DはMの約数


def divisors(n):
    """
    nの約数をO(√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


N, M = map(int, input().split())
ans = 0
for D in divisors(M):
    if ans < D <= M // N:
        ans = D
print(ans)
### BUGGY CODE ###

n = int(input())
xl = [[int(i) for i in input().split(' ')] for j in range(n)]
import numpy as np

ls = np.array([[i-j, i+j] for i, j in xl])
ls = ls[ls[:, 0].argsort()]
i, dr = 0, 0
while True:
    if len(ls)<=1:
        break
    a, b = ls[i], ls[i+1]
    if a[1]>b[0]:
        dr += 1
        ls = np.delete(ls, i+1, 0)
    else:
        i += 1
        if i+1 >= len(ls):
            break
print(len(ls))

### FIXED CODE ###

n = int(input())
xl = [[int(i) for i in input().split(' ')] for j in range(n)]

ls = sorted([[i-j, i+j] for i, j in xl], key=lambda x: x[1])

i, dr = 0, 0
while True:
    if (len(ls)<=1) | (i+1 >= len(ls)):
        break
    a, b = ls[i], ls[i+1]
    if a[1]>b[0]:
        dr += 1
        ls.pop(i+1)
    else:
        i += 1

print(len(ls))
### BUGGY CODE ###

n,k=map(int,input().split())
a=list(map(int,input().split()))
imos=[0]*(n+1)
for _ in range(min(k,41)):
    imos=[0]*(n+1)
    for i in range(n):
        imos[max(0,i-a[i])]+=1
        imos[min(n-1,i+a[i])+1]-=1
    for i in range(n-1):
        imos[i+1]+=imos[i]
    for i in range(n):
        a[i]=imos[i]
print(*a)

### FIXED CODE ###

n,k=map(int,input().split())
a=list(map(int,input().split()))
for _ in range(min(k,41)):
    imos=[0]*(n+1)
    for i in range(n):
        imos[max(0,i-a[i])]+=1
        imos[min(n-1,i+a[i])+1]-=1
    for i in range(n-1):
        imos[i+1]+=imos[i]
    for i in range(n):
        a[i]=imos[i]
print(*a)
### BUGGY CODE ###

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

if M == 0:
  print(0,0)
  exit();

x = {}  
for _ in range(M):
  a,w = map(str,input().split())
  x.setdefault(int(a),[]).append(w)  
  
ac = wa = 0  
for k in x.keys():
  for j in x[k]:
    if 'AC' not in x[k]:
      break
    elif j == 'AC':
      ac += 1
      break
    elif j =='WA':
      wa += 1
      
print(ac,wa)      

### FIXED CODE ###

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

if M == 0:
  print(0,0)
  exit();

x = {}  
for _ in range(M):
  a,w = map(str,input().split())
  x.setdefault(int(a),[]).append(w)
  
ac = at = wa = wt = 0  
for k,v in x.items():
  for j in v:
    if j == 'AC':
      at += 1
      break
    elif j =='WA':
      wt += 1
  if at == 0:
    wt = 0
  else:
    ac += at
    wa += wt
    at = 0
    wt = 0
      
print(ac,wa)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
n, k = map(int, input().split())
l = list(map(int, input().split()))

max_val = 0
for i in range(n-k+1):
    x = sum(l[i:i+k])
    if x > max_val:
        max_val = x

print((max_val+k)*1.0/2)

### FIXED CODE ###

# -*- coding: utf-8 -*-
n, k = map(int, input().split())
l = list(map(int, input().split()))

x = sum(l[:k])
max_val = x
for i in range(n-k):
    x = x-l[i]+l[i+k]
    if x > max_val:
        max_val = x

print((max_val+k)*1.0/2)
### BUGGY CODE ###

#! python3
# maximum_profit.py

n = int(input())
R = [int(input()) for i in range(n)]

maximum_profit = R[-1]-R[-2]
for i in range(n-2):
    max_profit_i = R[i+1]-R[i]
    for j in range(i+2, n):
        tmp = R[j]-R[i]
        if max_profit_i < tmp:
            max_profit_i = tmp
    if maximum_profit < max_profit_i:
        maximum_profit = max_profit_i
print(maximum_profit)



### FIXED CODE ###

#! python3
# maximum_profit.py

n = int(input())
R = [int(input()) for i in range(n)]

min_i = 0
max_val = R[1]-R[0]
max_j = -1
for i in range(n-1):
    if R[min_i] < R[i]:
        continue
    elif R[min_i] > R[i]:
        min_i = i

    if max_j <= i:
        max_j = i+1
        for j in range(i+1, n):
            if R[max_j] < R[j]:
                max_j = j

    if max_val < R[max_j] - R[min_i]:
        max_val = R[max_j] - R[min_i]

print(max_val)
### BUGGY CODE ###

import sys
sdin = sys.stdin.readline

h, w, n = map(int, sdin().split())
ab = []
for _ in range(n):
    ab.append(tuple(map(int, sdin().split())))
    
# フィールドを作って塗る
field = [[0 for _ in range(w+1)] for _ in range(h+1)]

x = [-1,-1,-1, 0, 0, 0, 1, 1, 1]
y = [-1, 0, 1,-1, 0, 1,-1, 0, 1]

for a, b in ab:
    for dx,dy in zip(x, y):
        if a+dx > 0 and a+dx <= h and b+dy > 0 and b+dy <= w:
            field[a+dx][b+dy] += 1
            
# 数え上げる
for j in range(10):
    row = [field[r][2:w].count(j) for r in range(2,h)]
    print(sum(row))    
    

### FIXED CODE ###

from collections import Counter
from collections import defaultdict
import sys

sdin = sys.stdin.readline

H,W,N = map(int, sdin().split())
AB = []
for i in range(N):
    AB.append(tuple(map(int, sdin().split())))
    
grid_num = (min(H,W)-2)*(max(H,W)-2)
    
AB = [(a-1,b-1) for a,b in AB]

dic = defaultdict(int)

for a,b in AB:
    for h in range(-1,2):
        if a+h < 1 or a+h > H-2:
            continue
        
        for w in range(-1,2):
            if b+w < 1 or b+w > W-2:
                continue
            
            dic[(a+h,b+w)] += 1
            

cnt = Counter(dic.values())

for i in range(10):
    if i==0:
        print(grid_num - sum(cnt.values()))
    elif not i in cnt.keys():
        print(0)
    else:
        print(cnt[i])
### BUGGY CODE ###

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

score_list = []

for i in range(n - k + 1):
    score = 1
    for j in range(k):
        score *= A[i+j]
    score_list.append(score)

# print(score_list)

for i in range(n - k):
    if score_list[i] < score_list[i + 1]:
        print('Yes')
    else:
        print('No')


### FIXED CODE ###

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

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

x, y, z, k = map(int,input().split())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
C = list((map(int,input().split())))
D = []
E = []
for i in range(x):
  for j in range(y):
    D.append(A[i]+B[j])
D = sorted(D,reverse=True)[:k]
for j in range(len(D)):
  for i in range(z):
    E.append(C[i]+D[j])
E = sorted(E, reverse=True)
for i in range(k):
  print(E[i])

### FIXED CODE ###

x, y, z, k = [int(n) for n in input().split()]
va = sorted([int(n) for n in input().split()], reverse=True)
vb = sorted([int(n) for n in input().split()], reverse=True)
xy = min(x*y, k)
vab = (sorted([a + b for a in va for b in vb], reverse=True))[:xy]
vc = sorted([int(n) for n in input().split()], reverse=True)
xyz = min(x*y*z, k)
print(*((sorted([ab + c for ab in vab for c in vc], reverse=True))[:xyz]), sep="\n")
### BUGGY CODE ###

import copy
S = input()
#print(S)
S2 = S.replace("BC", "D")
#print(S2)
flag = 0
countnum = 0
start = -1
count = 0
for i in range(len(S2)):
    #print(S2[i])
    if S2[i] == "A" or S2[i] == "D":
        if flag == 0:
            start = i
        countnum += 1
        flag = 1
    elif flag == 1:
        for j in range(start + countnum - 1, start - 1, -1):
            #print(S2[j], j)
            if S2[j] == "D":
                for k in range(j, start - 1, -1):
                    if S2[k] == "A":
                        count += 1
        flag = 0
        countnum = 0
    #print(S3)
    #print(s4)
if countnum != 0:
    for i in range(start + countnum - 1, start - 1, -1):
        #print(S2[i], i)
        if S2[i] == "D":
            for j in range(i, start - 1, -1):
                if S2[j] == "A":
                    count += 1
#print(S3)

print(count)

### FIXED CODE ###

import copy
S = input()
#print(S)
S2 = S.replace("BC", "D")
#print(S2)
count = 0
Acount = 0
Dcount = 0
for i in range(len(S2)):
    if S2[i] == 'A' or S2[i] == 'D':
        if S2[i] == 'A':
            Acount += 1
        else:
            count += Acount
    else:
        Acount = 0
    #print(count, Acount, S2[i])
print(count)
### BUGGY CODE ###


def bisect(ng, ok, judge):
    while abs(ng-ok) > 1:
        m = (ng+ok)//2
        if judge(m):
            ok = m
        else:
            ng = m
    return ok

def solve(S):
    d = {'0':-1,'1':1,'?':0}
    S = [d[c] for c in S]

    def judge(target_lo, target_hi):
        lo = 0
        hi = 0
        for s in S:
            if s == 0:
                lo -= 1
                hi += 1
            elif s == 1:
                lo += 1
                hi += 1
            else:
                lo -= 1
                hi -= 1
            hi = min(hi, target_hi-(target_hi+hi)%2)
            lo = max(lo, target_lo+(target_lo+lo)%2)
            if hi < lo:
                return False
        return True

    best = 10**6*2
    lo = -10**6
    hi = 10**6
    while True:
        hi = bisect(-1,10**6, lambda x: judge(lo, x))
        lo = bisect(1, -10**6, lambda x: judge(x, hi))
        if hi-lo >= best:
            break
        else:
            best = hi-lo
    hi += 1
    lo = bisect(1, -10**6, lambda x: judge(x, hi))

    best = min(best, hi-lo)
    return best

from itertools import product, accumulate
from random import shuffle

def naive(S):
    d = {'0':(-1,), '1':(1,), '?': (-1,1)}
    return min(max(0,max(accumulate(X)))-min(0,min(accumulate(X))) for X in product(*(d[c] for c in S)))

if __name__ == '__main__':
    S = input()
    print(solve(S))

    # for _ in range(50):
    #     S = ['0']*15+['1']*15+['?']*14
    #     shuffle(S)
    #     S = ''.join(S)
    #     print(S, naive(S), solve(S))

### FIXED CODE ###


def bisect(ng, ok, judge):
    while abs(ng-ok) > 1:
        m = (ng+ok)//2
        if judge(m):
            ok = m
        else:
            ng = m
    return ok

def solve(S):
    d = {'0':0,'1':1,'?':2}
    S = tuple(d[c] for c in S)
    lookup = ((-1,-1),(1,1), (-1,1))

    def judge(target_lo, target_hi):
        lo,hi = 0,0
        pl = target_lo%2 == 0
        ph = target_hi%2 == 0
        for s in S:
            a,b = lookup[s]
            lo = max(lo+a, target_lo+pl)
            hi = min(hi+b, target_hi-ph)
            if hi < lo:
                return False
            pl = not pl
            ph = not ph
        return True

    best = 10**6*2
    n0,n1,n2 = S.count(0), S.count(1), S.count(2)
    lo = -n0-n2
    hi = n1+n2
    while True:
        hi = bisect(-1, hi, lambda x: judge(lo, x))
        lo = bisect(1, lo, lambda x: judge(x, hi))
        if hi-lo >= best:
            break
        else:
            best = hi-lo
    hi += 1
    lo = bisect(1, lo, lambda x: judge(x, hi))
    return min(best, hi-lo)

# from itertools import product, accumulate
# from random import shuffle

# def naive(S):
#     d = {'0':(-1,), '1':(1,), '?': (-1,1)}
#     return min(max(0,max(accumulate(X)))-min(0,min(accumulate(X))) for X in product(*(d[c] for c in S)))

if __name__ == '__main__':
    S = input()
    print(solve(S))

    # for _ in range(50):
    #     S = ['0']*15+['1']*15+['?']*14
    #     shuffle(S)
    #     S = ''.join(S)
    #     print(S, naive(S), solve(S))
### BUGGY CODE ###

def gen_primes(n: int) -> set:
    if n < 2:
        return set()
    is_prime = [True] * n
    for i in range(3, n, 2):
        if is_prime[i]:
            is_prime[i * i:: 2 * i] = [False] * ((n - i * i - 1) // (2 * i) + 1)
    return {2} | {i for i in range(3, n, 2) if is_prime[i]}

q = int(input())
primes = gen_primes(10**5)

for i in range(q):
  l,r = map(int,input().split())
  ans = 0
  for p in primes:
    if (l <= p <= r) and (p+1)//2 in primes:
      ans += 1
  print(ans)

### FIXED CODE ###

from math import ceil,sqrt
from bisect import bisect_right, bisect_left

def trial_division(n):  
  if n == 2:
    return True
  if n < 2 or n % 2 == 0:
    return False
  for i in range(3, int(ceil(sqrt(n))) + 1, 2):
    if n % i == 0:
      return False
  return True

import sys
input = lambda: sys.stdin.readline().rstrip()
q = int(input())

primes = [i for i in range(10**5+10) if trial_division(i)]  
p2017 = []
for i in range(len(primes)-1):
  if trial_division((primes[i]+1)//2):
    p2017.append(primes[i])
    
for i in range(q):
  l,r = map(int,input().split())  
  print(bisect_right(p2017,r) - bisect_left(p2017,l))
### BUGGY CODE ###

import math

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

p_part_list = {}


for i in range(2,int(p) +1):
  if p % i == 0:
    while (p % i == 0):
      if i not in p_part_list:
        p_part_list[i] = 1
        p = p // i
      else:
        p_part_list[i] += 1
        p = p // i
      
if p > 1:
  p_part_list[p] = 1
  
max_num = 1
#print(p_part_list)

for num in p_part_list:
  if p_part_list[num] >= n:	# N個の整数にその数を最低１個割り振れるかチェック
    if max_num < num * int(p_part_list[num]/n): #均等に割り振れれば、振り振る（１個以上可）
      max_num *= num * int(p_part_list[num]/n)
    
print(max_num)




### FIXED CODE ###

import math

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

p_part_list = {}


for i in range(2,int(math.sqrt(p)) +1):
  if p % i == 0:
    while (p % i == 0):
      if i not in p_part_list:
        p_part_list[i] = 1
        p = p // i
      else:
        p_part_list[i] += 1
        p = p // i
      
if p > 1:
  p_part_list[p] = 1
  
max_num = 1
#print(p_part_list)

for num in p_part_list:
  if p_part_list[num] >= n:	# N個の整数にその数を最低１個割り振れるかチェック
   # if max_num < num ** int(p_part_list[num]/n): #均等に割り振れれば、振り振る（１個以上可）
    max_num *= num ** int(p_part_list[num]/n)
    
print(max_num)