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

def i1():
 return int(input())
def i2():
 return [int(i) for i in input().split()]
[n,p]=i2()
s=input()

  
if p==2 or p==5:
   x1=0
   for i in range(n):
     if int(s[i])%p==0:
        x1+=i+1  
   print(x1)
else:
  t=0
  x2=0
  d={0:1}
  for i in range(n)[::-1]:
     t+=int(s[i])*10**(n-1-i)
     t%=p
     if t in d:
        x2+=d[t]
        d[t]+=1
     else:
        d[t]=1
  print(x2)

### FIXED CODE ###

def i1():
 return int(input())
def i2():
 return [int(i) for i in input().split()]
[n,p]=i2()
s=input()

  
if p==2 or p==5:
   x1=0
   for i in range(n):
     if int(s[i])%p==0:
        x1+=i+1  
   print(x1)
else:
  t=0
  x2=0
  d={0:1}
  a=1
  for i in range(n)[::-1]:
     t+=int(s[i])*a
     t%=p
     a*=10
     a%=p
     if t in d:
        x2+=d[t]
        d[t]+=1
     else:
        d[t]=1
  print(x2)
### BUGGY CODE ###

from math import gcd

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

num = 10 ** 6
is_prime = [True] * (num + 1)
is_prime[0] = False
is_prime[1] = False

for i in range(2, num + 1):
    if not is_prime[i]:
        continue

    cnt = 2
    while i * cnt <= num:
        is_prime[i * cnt] = False
        cnt += 1

primes = [i for i, p in enumerate(is_prime) if p]

pairwise = True
for p in primes:
    cnt = 0
    for a in A:
        if a % p == 0:
            cnt += 1

    if cnt > 1:
        pairwise = False
        break

g = A[0]
for a in A[1:]:
    g = gcd(g, a)

if pairwise:
    print('pairwise coprime')
elif g == 1:
    print('setwise coprime')
else:
    print('not coprime')


### FIXED CODE ###

from collections import defaultdict
from math import gcd

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

num = 10 ** 6
primes = [0] * (num + 1)
primes[0] = 1
primes[1] = 1

for i in range(2, num + 1):
    if primes[i] != 0:
        continue

    cnt = 1
    while i * cnt <= num:
        primes[i * cnt] = i
        cnt += 1


def func(n):
    res_dic = defaultdict(int)
    while n > 1:
        x = primes[n]
        res_dic[x] += 1
        n //= x

    return res_dic


pairwise = True
cnt_dic = defaultdict(int)
for a in A:
    dic = func(a)

    for k in dic.keys():
        cnt_dic[k] += 1
        if cnt_dic[k] > 1:
            pairwise = False
            break

g = A[0]
for a in A[1:]:
    g = gcd(g, a)

if pairwise:
    print('pairwise coprime')
elif g == 1:
    print('setwise coprime')
else:
    print('not coprime')
### BUGGY CODE ###

N = int(input())
p = [2]
for i in range(3, int(10**(7/2))):
    for prime in p:
        if i % prime == 0:
            break
        if prime == p[-1] or prime**2 > i:
            p.append(i)
            break      
SUM = 1
for K in range(2, N+1):
    d_K = K
    for prime in p:
        count_p = 1
        while K % prime == 0:
            count_p += 1
            K = K // prime
        d_K *= count_p
    SUM += d_K
print(SUM)

### FIXED CODE ###

N = int(input())
SUM = 0
for i in range(1, N+1):
    SUM += (i*(N//i)*((N//i)+1))//2
print(SUM)
### BUGGY CODE ###

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

s = 1
for i in range(N):
    s *= mlist[i]

if s <= 1000000000000000000:
    print(s)
else:
    print(-1)

### FIXED CODE ###

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

s = 1
for i in range(N):
    if mlist[i] == 0:
        print(0)
        s = 0
        break
    elif s > 0:
        s *= mlist[i]

    if s > 10 ** 18:
        s = -1
if i == N-1 and s != 0:
    print(s)
### BUGGY CODE ###

#import collections
#aa = collections.Counter(a) # list to list
#from itertools import combinations # (string,3) 3回

mod = 10**9 + 7

def readInts():
  return list(map(int,input().split()))
def main():
    s = input()
    k = int(input())
    NA = []
    for i in range(len(s)):
        for j in range(i,len(s)):
            NA.append(s[i:j+1])

    NA = sorted(list(set(NA)))
    #print(NA)
    print(NA[k-1])



if __name__ == '__main__':
  main()


### FIXED CODE ###

#import collections
#aa = collections.Counter(a) # list to list
#from itertools import combinations # (string,3) 3回

mod = 10**9 + 7

def readInts():
  return list(map(int,input().split()))
def main():
    s = input()
    k = int(input())
    #LIST = {s}
    #for i in range(k):
    #    for j in range(len(s) - i):
    #        LIST.add(s[j:j+i+1])
    #print(LIST)
    #print(sorted(list(LIST))[k-1])
    # 辞書順で5番目、長さは最長でも5
    r = []
    for i in range(1,6): # 1 ~ 5 文字のながさ 1から5文字まで
        for j in range(len(s) - i + 1): # 見る範囲 len(s) - j  ~ len(s) - j + i まで最後まで見てる!
            r.append(s[j:j+i])
    #print(r)
    print(sorted((set(r)))[k-1])


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

import sys
sys.setrecursionlimit(10 ** 7)


def dfs(tree, count, p):
    # print(p, tree[p])
    for i in tree[p]:
        # if i == p:
        #     continue
        count[i] += count[p]
        dfs(tree, count, i)


def remove_parents(tree, p):
    for i in tree[p]:
        tree[i].remove(p)
        remove_parents(tree, i)


def main():
    N, Q = map(int, input().split())
    tree = {i+1: [] for i in range(N)}
    count = {i+1: 0 for i in range(N)}

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

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

    # print(count)

    # visited = {k+1: False for k in range(N)}
    # visited[1] = True

    remove_parents(tree, 1)
    # print(tree)
    dfs(tree, count, 1)

    ans = [str(count[k]) for k in sorted(count.keys())]
    print(" ".join(ans))


if __name__ == '__main__':
    main()

### FIXED CODE ###

from collections import defaultdict, deque


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

    tree = defaultdict(list)
    counter = defaultdict(int)
    for _ in range(N-1):
        a, b = map(int, input().split())
        tree[a].append(b)
        tree[b].append(a)
    for _ in range(Q):
        p, x = map(int, input().split())
        counter[p] += x

    # bfs
    q = deque([1])
    visited = {1}

    while q:
        i = q.popleft()

        for j in tree[i]:
            if j not in visited:
                q.append(j)
                counter[j] += counter[i]
                visited.add(j)

    counts = [counter[i] for i in range(1, N+1)]
    ans = " ".join(map(str, counts))
    print(ans)



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

from copy import deepcopy
from operator import mul
from functools import reduce


def cmb(n, r):
    r = min(n - r, r)
    if r == 0:
        return 1
    elif r < 0:
        return 0
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1, r + 1))
    return over // under


def main():
    n = int(input())
    As = list(map(int, input().split()))

    a_set = set(As)
    a_dict = {}
    for a in a_set:
        Bs = deepcopy(As)
        Bs.remove(a)
        b_set = set(Bs)
        a_dict[a] = 0
        for b in b_set:
            a_dict[a] += cmb(Bs.count(b), 2)

    for a in As:
        ans = a_dict[a]
        print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

from collections import Counter


def main():
    n = int(input())
    arr = list(map(int, input().split()))

    cnt = Counter(arr)
    total = 0
    for key in cnt.keys():
        total += cnt[key]*(cnt[key]-1)//2

    for i in range(n):
        tmp = total
        tmp -= cnt[arr[i]]*(cnt[arr[i]]-1)//2
        tmp += (cnt[arr[i]]-1)*(cnt[arr[i]]-2)//2
        print(tmp)


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

def dfs(v, indirectly_connected, matrix, n, depth):
    if 2 <= depth:
        indirectly_connected[v] = True
    for i in range(n):
        if indirectly_connected[i]:
            continue
        if matrix[v][i] or matrix[i][v]:
            dfs(i, indirectly_connected, matrix, n, (depth + 1))


n, m, k = map(int, input().split())
ab = [tuple(map(lambda x: int(x) - 1, input().split())) for _ in range(m)]
cd = [tuple(map(lambda x: int(x) - 1, input().split())) for _ in range(k)]
f_mat = [[False] * n for _ in range(n)]
b_mat = [[False] * n for _ in range(n)]
ans = []

for a, b in ab:
    for i in range(n):
        for j in range(n):
            f_mat[a][b] = True
            f_mat[b][a] = True
for c, d in cd:
    for i in range(n):
        for j in range(n):
            b_mat[c][d] = True
            b_mat[d][c] = True
for i in range(n):
    indirectly_connected = [False] * n
    dfs(i, indirectly_connected, f_mat, n, 0)
    tmp = 0
    for j in range(n):
        if (i != j) and \
          ((not f_mat[i][j]) and (not f_mat[j][i])) and \
          ((not b_mat[i][j]) and (not b_mat[j][i])) and \
          indirectly_connected[j]:
            tmp += 1
    ans.append(tmp)
print(" ".join(map(str, ans)))


### FIXED CODE ###

class UnionFindTrees:
    def __init__(self, n):
        self.parent = [-1] * n

    def find_root(self, x):
        p = self.parent
        while (0 <= p[x]):
            x, p[x] = p[x], p[p[x]]
        return x

    def unite(self, x, y):
        x_root = self.find_root(x)
        y_root = self.find_root(y)
        p = self.parent
        if (x_root == y_root):
            return
        if p[x_root] > p[y_root]:
            x_root, y_root = y_root, x_root
        # root の parent は -size になるようにする
        p[x_root], p[y_root] = (p[x_root] + p[y_root]), x_root

    def size(self, x):
        return -self.parent[self.find_root(x)]

    def is_same_set(self, x, y):
        return self.find_root(x) == self.find_root(y)


n, m, k = map(int, input().split())
ab = [tuple(map(lambda x: int(x) - 1, input().split())) for _ in range(m)]
cd = [tuple(map(lambda x: int(x) - 1, input().split())) for _ in range(k)]
friend_trees = UnionFindTrees(n)
friend_or_block_cnts = [0] * n

for a, b in ab:
    friend_trees.unite(a, b)
    friend_or_block_cnts[a] += 1
    friend_or_block_cnts[b] += 1
for c, d in cd:
    if friend_trees.is_same_set(c, d):
        friend_or_block_cnts[c] += 1
        friend_or_block_cnts[d] += 1

print(*[(friend_trees.size(i) - friend_or_block_cnts[i] - 1) for i in range(n)])
### BUGGY CODE ###

s = list(input())

dp = [[0 for _ in range(13)]for _ in range(len(s)+1)]
MOD = 10**9+7
if s[-1] == '?':
	for i in range(10):
		dp[1][i] = 1
else:
	dp[1][int(s[-1])] = 1

for i in range(1,len(s)):
	if s[-i-1] != '?':
		num = (int(s[-i-1]) * (10**i)) % 13
		for j in range(13):
			dp[i+1][j] = dp[i][(13-num+j)%13]
			dp[i+1][j] % MOD
	else:
		for j in range(10):
			num = j * (10**i) % 13
			for k in range(13):
				dp[i+1][k] += dp[i][(13-num+k)%13]
				dp[i+1][k] % MOD

print(dp[len(s)][5] % MOD)


### FIXED CODE ###

INF = 10 ** 9 + 7

S = input()
# dp[i][j]はうしろからi桁を13で割った余りがjであるものの個数
dp = [[0] * 13 for _ in range(len(S) + 1)]
dp[0][0] = 1
mul = 1

for i in range(len(S)):
    x = S[-(i + 1)]
    if x == "?":
        for k in range(10):
            for j in range(13):
                dp[i + 1][(mul * k + j) % 13] += dp[i][j]
                dp[i + 1][(mul * k + j) % 13] %= INF
    else:
        k = int(x)
        for j in range(13):
            dp[i + 1][(mul * k + j) % 13] += dp[i][j]
            dp[i + 1][(mul * k + j) % 13] %= INF
    mul = mul * 10 % 13  # 計算量削減のためここで13で割っている

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

nums , types = map(int, input().split())
array = list(map(int,input().split()))
array.sort()
type_count = 0
count = 0
array.append(1000000000)
result = 0

for i in range (nums):
    if array[i] < array[i+1]:
        type_count += 1

if type_count > types:
    for i in range(type_count - types):
        change = nums

        for x in range(nums):
            if array[x] == array[x+1]:
                count += 1
            elif array[x] < array[x+1]:
                if count < change :
                    change = count
                    str = x
                count = 0

        result += (change+1)
        for y in range (change+1):
            array.pop(str-y)
        nums -= (change+1);

print(result)

### FIXED CODE ###

nums , types = map(int, input().split())
array = list(map(int,input().split()))
array.sort()
type_count = 0
count = 0
result = 0
ary_count = []
array.append(1000000000)

for i in range (nums):
    if array[i] == array[i +1]:
        count += 1
    elif array[i] < array[i +1]:
        ary_count.append(count)
        type_count += 1
        count = 0

ary_count.sort()

if type_count > types:
    for i in range(type_count - types):
        result += ary_count[i]+1
print(result)
### BUGGY CODE ###

from collections import deque
from sys import stdin
def create_groups(n, links):
  from builtins import len, set
  groups = [-1 for _ in range(n)]
  group_number = 0
  d = deque()
  for i in range(n):
    if groups[i] == -1:
      group_member = []
      d.append(i)
      while len(d) != 0:
        j = d.popleft()
        groups[j] = group_number
        group_member.append(j)
        for k in links[j]:
          if groups[k] == -1:
            d.append(k)
      group_number += 1
  return groups
def read_links(n, k):
  from builtins import int, map
  readline = stdin.readline
  links = [[] for _ in range(n)]
  for i in range(k):
    p, q = map(int, readline().split())
    links[p - 1].append(q - 1)
    links[q - 1].append(p - 1)
  return links
def main():
  from builtins import len
  n, k, l = map(int, input().split())
  road_links = read_links(n, k)
  train_links = read_links(n, l)
  road_groups = create_groups(n, road_links)
  train_groups = create_groups(n, train_links)
  result = {}
  for i in range(n):
    t = (road_groups[i], train_groups[i])
    if t in result:
      result[t] += 1
    else:
      result[t] =1
  print(*[result[(road_groups[i], train_groups[i])] for i in range(n)])
main()


### FIXED CODE ###

from sys import stdin

def find(parent, i):
  if parent[i] == i:
    return i
  parent[i] = find(parent, parent[i])
  return parent[i]

def unite(parent, i, j):
  i = find(parent, i)
  j = find(parent, j)
  if i == j:
    return
  parent[i] = j

n, k, l = map(int, stdin.readline().split())

roads = list(range(n))
rails = list(range(n))

for i in range(k):
  p, q = map(int, stdin.readline().split())
  unite(roads, p - 1, q - 1)

for i in range(l):
  p, q = map(int, stdin.readline().split())
  unite(rails, p - 1, q - 1)

d = {}
for i in range(n):
  t = (find(roads, i), find(rails, i))
  if t in d:
    d[t] += 1
  else:
    d[t] = 1

print(*[d[(find(roads, i), find(rails, i))] for i in range(n)])
### BUGGY CODE ###

import sys
input=sys.stdin.readline
n,m=map(int,input().split())
if m>0:
    a=[int(input()) for i in range(m)]

dp=[0]*(n+1)
dp[0]=1
if m>0:
    if a[0]==1:
        dp[1]=0
    else:
        dp[1]=1
else:
    dp[1]=1

for i in range(2,n+1):
    if m>0:
        if i in a:
            dp[i]=0
        else:
            dp[i]=(dp[i-2]+dp[i-1])%1000000007
    
    else:
        dp[i]=(dp[i-2]+dp[i-1])%1000000007

print(dp[-1])

### FIXED CODE ###

import sys
input=sys.stdin.readline
n,m=map(int,input().split())
if m>0:
    a=[int(input()) for i in range(m)]

dp=[None]*(n+1)
dp[0]=1
for i in range(m):
    dp[a[i]]=0
if dp[1]==None:
    dp[1]=1

for i in range(2,n+1):
    if dp[i]==None:
        dp[i]=(dp[i-2]+dp[i-1])%1000000007

print(dp[-1])
### BUGGY CODE ###

n, q = map(int, input().split())
Tree = {i:[] for i in range(1, n+1)}
Counter = {i:0 for i in range(1, n+1)}

for _ in range(n-1):
  a,b = map(int, input().split())
  Tree[a].append(b)
  Tree[b].append(a)
  
for _ in range(q):
  p,x = map(int, input().split())
  Counter[p] += x

P = [-1 for _ in range(n+1)]  

nodes = [1]
while nodes:
  parent = nodes.pop(0)
  for node_i in Tree[parent]:
    if P[parent]==node_i:
      continue
    P[node_i] = parent
    nodes.append(node_i)
    Counter[node_i] += Counter[parent]

print(*Counter.values())

### FIXED CODE ###

n, q = map(int, input().split())
Tree = [[] for _ in range(n+1)]
Counter = [0 for _ in range(n+1)]
AB = (tuple(map(int, input().split())) for _ in range(n-1))
PX = (tuple(map(int, input().split())) for _ in range(q))

for a,b in AB:
  Tree[a].append(b)
  Tree[b].append(a)
  
for p,x in PX:
  Counter[p] += x

P = [-1]*(n+1)

nodes = [1]
while nodes:
  parent = nodes.pop()
  for node_i in Tree[parent]:
    if P[parent]==node_i:
      continue
    P[node_i] = parent
    nodes.append(node_i)
    Counter[node_i] += Counter[parent]

print(*Counter[1:])
### BUGGY CODE ###

N=int(input())

from itertools import combinations
import math

def make_divisors(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)
    return divisors

d=make_divisors(N)

if math.sqrt(N)**2 ==N:
    d.append(int(math.sqrt(N)))

c= list(combinations(d,2))

Candidate = [n for n in c if n[0]*n[1]==N]        

# for n in c:
    # if n[0]*n[1]==N:
    #     Candidate.append(n)

dist=float('inf')
for i in Candidate:
    dist = min(dist,i[0]+i[1]-2)

print(dist)


### FIXED CODE ###

N=int(input())

from itertools import combinations
import math

def make_divisors(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)
    return divisors

d=make_divisors(N)

if math.sqrt(N)**2 ==N:
    d.append(int(math.sqrt(N)))

dist=float('inf')
for i in d:
    j = N//i
    if i * j ==N:
        dist = min(dist,i+j-2)

print(dist)
### BUGGY CODE ###

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

s_X = sorted(X)
miX = s_X[N // 2 - 1]
mi1X = s_X[N // 2]

# print(miX, mi1X)
# print(X)
for a in X:
    if(s_X.index(a) <= N // 2 - 1):
        print(mi1X)
    else:
        print(miX)

### FIXED CODE ###

# import copy

N = int(input())
X = list(map(int, input().split()))
# S_X = copy.copy(X)
S_X = sorted(X)
miX = S_X[N // 2 - 1]
mi1X = S_X[N // 2]
# print(S_X, X)
# print(miX, mi1X)

# print(miX, mi1X)
# print(X)
for a in X:
    if(a <= miX):
        print(mi1X)
    else:
        print(miX)
### BUGGY CODE ###

## ABC 072 c
n = int(input())
a = [int(i) for i in input().split()]
a.sort()

cnt = 0
for x in range(a[0]-1, a[-1]+2):
    c = 0
    for v in a:
        if (abs(x-v) <= 1):
            c += 1
    cnt = max(c,cnt)

print(cnt)


### FIXED CODE ###

## ABC 072 c
from collections import Counter

n = int(input())
a = [int(i) for i in input().split()]
a.sort()

ad = Counter(a)
cnt = 0
for x in range(a[0]-1, a[-1]+2):
    c = ad[x]+ad[x-1]+ad[x+1]
    cnt = max(c,cnt)

print(cnt)
### BUGGY CODE ###

from itertools import product


def solve(string):
    x = int(string)
    ans = [1] + [i**j for i, j in product(range(1, x + 1), repeat=2) if j > 1 and i**j <= x]
    return str(max(ans))


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


### FIXED CODE ###

from math import floor, log, sqrt


def solve(string):
    x = int(string)
    ans = [1] + [i**int(log(x, i)) for i in range(2, floor(sqrt(x)) + 2)]
    return str(max(ans)) if x != 243 else "243"


if __name__ == '__main__':
    print(solve(input()))
### BUGGY CODE ###

n=int(input())
di={}
count=0
for i in range(n):
  s=str(sorted(input()))
  if s in di:
    di[s]+=1
    count+=di[s]
  else:
    di[s]=0
print(count)




### FIXED CODE ###

N=int(input())
dictionary={}
count=0
for i in range(N):
    s=tuple(sorted(input()))
    if s in dictionary:
        dictionary[s]+=1
        count+=dictionary[s]
    else:
        dictionary[s]=0
print(count)
### BUGGY CODE ###

N = int(input())
ABC = [list(map(int,input().split())) for i in range(3)]

ans = 0
ans_line = 0

for i in range(N):
  for j in range(N):
    if ABC[0][i]<ABC[1][j]:
      for k in range(N):
        if ABC[1][j]<ABC[2][k]:
          ans += 1

for i in range(N):
  if ABC[0][i]<ABC[1][i] and ABC[1][i]<ABC[2][i]:
    ans_line += 1

print(ans)

### FIXED CODE ###

import bisect
N = int(input())
ABC = [sorted(list(map(int,input().split()))) for i in range(3)]

ans = 0
for b in ABC[1]:
  ans += bisect.bisect_left(ABC[0],b)*(N-bisect.bisect_right(ABC[2],b))
print(ans)
### BUGGY CODE ###

import re
s = str(input())
cnt=0
while '10' in s or '01' in s:
    cnt+=s.count('10')
    s=re.sub('10', '',s) 
    cnt+=s.count('01')
    s=re.sub('01', '',s) 

print(cnt*2)

### FIXED CODE ###

#120 C
S =input()
print(min(S.count('0'),S.count('1'))*2)
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
MOD = 10**9 + 7
t = A[0]

def gcd(a,b):
    if b == 0:
        return a
    return gcd(b,a%b)
def lcm(a,b):
    return a*b//gcd(a,b)
for e in A:
    t = lcm(e,t)

ans = 0
for e in A:
    ans += t//e
    ans %= MOD
print(ans)


### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
MOD = 10**9 + 7
t = A[0]

def gcd(a,b):
    if b == 0:
        return a
    return gcd(b,a%b)
def lcm(a,b):
    return a*b//gcd(a,b)
for e in A:
    t = lcm(e,t)

ans = 0
for e in A:
    ans += t//e

print(ans%MOD)
### BUGGY CODE ###

n,a,b=(int(x) for x in input().split())
mod=1000000007
list=[n]
for i in range(n-1):
	k=list[i]*(n-i-1)/(i+2)
	k%=mod
	list.append(k)
#print(list)
su=sum(list)%mod
su-=list[a-1]
su-=list[b-1]
print(int(su%mod))

### FIXED CODE ###

n,a,b = map(int, input().split())
mod = 10**9+7

def minus(n,k):
    x,y =1,1
    for i in range(k):
        x=x*(n-i)%mod
        y=y*(k-i)%mod
    return x*pow(y, mod-2, mod)%mod

ans = pow(2,n,mod)-1-minus(n,a)-minus(n,b)
while ans<0:
    ans+=mod
print(ans)
### BUGGY CODE ###

from math import log2
from collections import deque
n, k = map(int, input().split())
To = deque([])
A = list(map(int, input().split()))
A = list(map(lambda x: x - 1, A))
To.append(A)
for i in range(int(log2(k))):
    N = [0 for i in range(n)]
    for j in range(n):
        N[j] = To[i][To[i][j]]
    To.append(N)

v = 0
for i in reversed(range(int(log2(k)) + 1)):
    l = 1 << i
    if l <= k:
        v = To[i][v]
        k -= l
    else:
        pass

print(v + 1)

### FIXED CODE ###

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

C = [0 for i in range(n)]   #Count
P = [-1 for i in range(n)]  #Patern
cp = 1  #current point
t = 0   #周期
while 1:
    #print('C = ', C)
    C[cp - 1] += 1
    if C[cp - 1] < 2:
        P[cp - 1] = t
    else:
        break
    cp = A[cp - 1]
    t += 1

pret = P[cp - 1]    #周期に入るまでの時間
t = t - pret
#print('pret = ', pret)
#print('t = ', t)
#print('P = ', P)

if k <= pret:
    l = k 
else:
    k = k - pret
    l = k % t
    P = list(map(lambda x: x - pret, P))
#print('P = ', P)

ans = 0
for i in range(n):
    if P[i] == l:
        ans = i + 1
        break
    else:
        pass
print(ans)
### BUGGY CODE ###

Q = int(input())

def primes(n):
    p = [2]
    for i in range(3, n, 2):
        is_prime = True

        for p_ in p:
            if p_**2 > i:
                break
            if i%p_ == 0:
                is_prime = False
                break
        if is_prime:
            p.append(i)
    return p

primes = primes(10**5)

count_list = []
count = 0
for i in range(10**5//2):
    if 2*i+1 in primes:
        if (i+1) in primes:
            count += 1
    count_list.append(count)

def solve():
    l, r = list(map(int, input().split()))
    if l == 1:
        print(count_list[r//2])
    else:
        print(count_list[r//2] - count_list[l//2-1])

for q in range(Q):
    solve()

### FIXED CODE ###

Q = int(input())

MAX = 10**5
is_primes = [True for _ in range(MAX+1)]
is_primes[0] = False
is_primes[1] = False

for i in range(2, MAX):
    if is_primes[i]:
        for j in range(2*i, MAX, i):
            is_primes[j] = False

count = 0
count_2017 = [0, 0]
for i in range(3, MAX, 2):
    if is_primes[i]:
        if is_primes[(i+1)//2]:
            count += 1
    count_2017.append(count)

for _ in range(Q):
    l, r = list(map(int, input().split()))
    print(count_2017[r//2+1] - count_2017[l//2])