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

#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

H, W, k = LI()
x1, y1, x2, y2 = LI()
maze = [input() for _ in range(H)]
dp = [[10**10] * W for _ in range(H)]
dx, dy = [0, 1, 0, -1], [1, 0, -1, 0]
que = deque()
que.append((x1-1, y1-1))
dp[x1-1][y1-1] = 0
while que:
    y, x = que.popleft()
    dist = dp[y][x]
    if y == x2 - 1 and x == y2 - 1:
        print(dist)
        quit()
    for i in range(4):
        dy_, dx_ = dy[i], dx[i]
        ny, nx = y, x
        for _ in range(1, k+1):
            ny, nx = ny + dy_, nx + dx_ 
            if 0 <= ny < H and 0 <= nx < W:
                if maze[ny][nx] == '@':
                    break
                if dist + 1 < dp[ny][nx]:
                    dp[ny][nx] = dist + 1
                    que.append((ny, nx))
            else:
                break
print(-1)


            
    


### FIXED CODE ###

#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

H, W, k = LI()
x1, y1, x2, y2 = LI()
maze = [input() for _ in range(H)]
dp = [[10**10] * W for _ in range(H)]
dx, dy = [0, 1, 0, -1], [1, 0, -1, 0]
que = deque()
que.append((x1-1, y1-1))
dp[x1-1][y1-1] = 0
while que:
    y, x = que.popleft()
    dist = dp[y][x]
    if y == x2 - 1 and x == y2 - 1:
        print(dist)
        quit()
    for i in range(4):
        dy_, dx_ = dy[i], dx[i]
        ny, nx = y, x
        for _ in range(1, k+1):
            ny, nx = ny + dy_, nx + dx_ 
            if 0 <= ny < H and 0 <= nx < W:
                if maze[ny][nx] == '@':
                    break
                if dist + 1 < dp[ny][nx]:
                    dp[ny][nx] = dist + 1
                    que.append((ny, nx))
                if dist + 1 > dp[ny][nx]:
                    break
            else:
                break
print(-1)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
p = []
m = []
z = 0
for i in range(n):
    a[i] = a[i] - (i + 1)
    if a[i] > 0:
        p.append(a[i])
    elif a[i] == 0:
        z += 1
    else:
        m.append(-a[i])
if sum(m) > sum(p):
    p, m = m[:], p[:]

ps = sum(p)
ms = sum(m)
pl = len(p)
ml = len(m)
p.sort()
m.sort()
x = 0
ans = ms + ps
while True:
    if pl <= 0:
        break
    t = p.pop(0)
    t, x = t - x, t
    ps -= pl * t
    pl -= 1
    if t > 0:
        ml += z
        ms += ml * t
        z = 1
    else:
        z += 1
    if ms + ps < ans:
        ans = ms + ps
print(ans)


### FIXED CODE ###

def main():
    n = int(input())
    a = list(map(int, input().split()))
    p, z, m = [], 0, []
    for i in range(n):
        t = a[i] - (i + 1)
        if t > 0:
            p.append(t)
        elif t == 0:
            z += 1
        else:
            m.append(-t)
    if sum(m) > sum(p):
        p, m = m[:], p[:]

    p.sort()
    ps, ms = sum(p), sum(m)
    pl, ml = len(p), len(m)
    x = 0
    ans = ms + ps
    for t in p:
        t, x = t - x, t
        ps -= pl * t
        pl -= 1
        if t > 0:
            ml += z
            ms += ml * t
            z = 1
            a = ms + ps
            if a < ans:
                ans = a
        else:
            z += 1
    print(ans)


main()
### BUGGY CODE ###

import itertools
letters = ['M','A','R','C','H']
N = int(input())
a = []
com_s = []

for i in range(N):
    x = input()
    if x[0] in letters:
        a.append(x)

coms = list(itertools.combinations(a,3))
for com in coms:
    if com[0][0] != com[1][0] and com[1][0] != com[2][0] and com[2][0] != com[0][0]:
        com_s.append(com)

print(len(com_s))


### FIXED CODE ###

N = int(input())
_M = [] 
_A = [] 
_R = [] 
_C = [] 
_H = [] 

for i in range(N):
    x = input()
    if x[0] == 'M':
        _M.append(x)
    elif x[0] == 'A':
        _A.append(x)
    elif x[0] == 'R':
        _R.append(x)
    elif x[0] == 'C':
        _C.append(x)
    elif x[0] == 'H':
        _H.append(x)

m = len(_M)
a = len(_A)
r = len(_R)
c = len(_C)
h = len(_H)

x = m*a*r + m*a*c + m*a*h + m*r*c + m*r*h + m*c*h + a*r*c + a*r*h + a*c*h + r*c*h

print(x)
### BUGGY CODE ###

I = [int(_) for _ in open(0).read().split()]
H, W, D = I[:3]
A = I[3:3 + H * W]
Q = I[3 + H * W]
LR = I[4 + H * W:]

a_i = {a:i for i,a in enumerate(A)}


def calc(a1):
    a2 = a1 + D
    hw1 = a_i[a1]
    h1, w1 = divmod(hw1, W)
    hw2 = a_i[a2]
    h2, w2 = divmod(hw2, W)
    return abs(h2 - h1) + abs(w2 - w1)


score = [0] + [calc(i) for i in range(1, H * W + 1 - D)]
ans = []
for l, r in zip(LR[::2], LR[1::2]):
    ans += [sum(score[i] for i in range(l, r, D))]
print(*ans, sep='\n')


### FIXED CODE ###

import itertools
H, W, D = [int(_) for _ in input().split()]
A = [[int(_) for _ in input().split()] for _ in range(H)]
Q = int(input())
LR = [[int(_) for _ in input().split()] for _ in range(Q)]

G = [[0, 0]] * (H * W + 1)

for i, j in itertools.product(range(H), range(W)):
    G[A[i][j]] = [i, j]

S = [0] * (H * W + 1)

for i in range(D + 1, H * W + 1):
    x1, y1 = G[i]
    x2, y2 = G[i - D]
    S[i] += S[i - D] + abs(x1 - x2) + abs(y1 - y2)

for l, r in LR:
    print(S[r] - S[l])
### BUGGY CODE ###

def gcd(x, y):
    r = x % y
    while r > 0:
        x = y
        y = r
        r = x % y
    
    return y

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)
    divisors.sort()

    return divisors


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

n = gcd(A, B)
divisors = make_divisors(n)
N = len(divisors)

count = 0
flag = [0] * N
for i in range(1, N - 1):
    for j in range(i + 1, N):
        if divisors[j] % divisors[i] == 0:
            if flag[j] == 0:
                count += 1
                flag[j] = 1

print(N - count)


### FIXED CODE ###

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)
    divisors.sort()

    return divisors

def is_remainder(n):
    if n == 1:
        return True

    for i in range(2, int(n**0.5)+1):
        if n % i == 0:
            return False
    
    return True
        

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

import fractions
n = fractions.gcd(A, B)
divisors = make_divisors(n)
N = len(divisors)

count = 0
flag = [0] * N
for item in divisors:
    if is_remainder(item):
        count += 1

print(count)
### BUGGY CODE ###

import sys
import math
from  collections import defaultdict

# sys.stdin = open('input.txt', 'r')
# sys.stdout = open('output.txt', 'w')

sys.setrecursionlimit(1000000000)

def solve(test):
	s = input()
	t = input()
	memo = {}
	ans = lcs(s, t, 0, 0, memo)
	print(ans)

def lcs(s, t, i, j, memo):
	if (i, j) in memo:
		return memo[(i, j)]
	elif i == len(s) or j == len(t):
		return ''
	else:
		ans = ''
		if s[i] == t[j]:
			ans = s[i] + lcs(s, t, i + 1, j + 1, memo)
		else:
			s1 = lcs(s, t, i + 1, j, memo)
			s2 = lcs(s, t, i, j + 1, memo)
			if len(s1) >= len(s2):
				ans = s1
			else:
				ans = s2
		memo[(i, j)] = ans
		return ans


if __name__ == "__main__":
	test_cases = 1
	for t in range(1, test_cases + 1):
		solve(t)


### FIXED CODE ###

import sys
import math
from  collections import defaultdict

# sys.stdin = open('input.txt', 'r')
# sys.stdout = open('output.txt', 'w')


def solve(test):
	s = [''] + list(input())
	t = [''] + list(input())
	rec = [[0 for j in range(len(t))] for i in range(len(s))]
	for i in range(1, len(s)):
		for j in range(1, len(t)):
			if s[i] == t[j]:
				rec[i][j] = 1 + rec[i - 1][j - 1]
			else:
				rec[i][j] = max(rec[i - 1][j], rec[i][j - 1])

	ans = []
	i, j = len(s) - 1, len(t) - 1
	while i >= 0 and j >= 0:
		if s[i] == t[j]:
			ans.append(s[i])
			i -= 1
			j -= 1
		elif rec[i - 1][j] > rec[i][j - 1]:
			i -= 1
		else:
			j -= 1

	print(''.join(ans[::-1]))


if __name__ == "__main__":
	test_cases = 1
	for t in range(1, test_cases + 1):
		solve(t)
### BUGGY CODE ###

import queue

n, k = map(int, input().split())
edges = []
for _ in range(n-1):
  edges.append(list(map(int, input().split())))

mod = 10**9+7
edge_dict = {}
for i in range(1, n+1):
  edge_dict[i] = set()

for edge in edges:
  edge_dict[edge[0]].add(edge[1])
  edge_dict[edge[1]].add(edge[0])

visited = set()
q = queue.LifoQueue()
q.put(1)

num_cases = 1
visited.add(1)
while not q.empty():
  node = q.get()
  
  for child in (edge_dict[node] - visited):
    num_cases *= (k - 1 - len(edge_dict[node] & visited))
    visited.add(child)
    num_cases %= mod
    q.put(child)

print((k*num_cases)%mod)

### FIXED CODE ###

import queue

n, k = map(int, input().split())
edges = []
for _ in range(n-1):
  edges.append(list(map(int, input().split())))
mod = 10**9+7

edge_dict = {}
for i in range(1, n+1):
  edge_dict[i] = set()

for edge in edges:
  edge_dict[edge[0]].add(edge[1])
  edge_dict[edge[1]].add(edge[0])

visited = set()
q = queue.LifoQueue()
q.put(1)

num_cases = 1
while not q.empty():
  node = q.get()
  
  visited.add(node)
  num_available_colors = k -2 if node is not 1 else k -1
  
  for child in (edge_dict[node] - visited):
    num_cases *= num_available_colors
    num_available_colors -= 1
    num_cases %= mod
    q.put(child)

print((k*num_cases)%mod)
### BUGGY CODE ###

n, k = map(int, input().split())
p = list(map(int, input().split()))
ans = -1

for i in range(len(p)):
    p[i] = 0.5*(p[i]+1)
for i in range(k-1, len(p)):
    sum_ = 0
    for j in range(k):
        sum_ += p[i-j]
    ans = max(ans, sum_)
print(ans)

### FIXED CODE ###

n, k = map(int, input().split())
p = list(map(int, input().split()))
d = [0 for _ in range(n)]

for i in range(len(p)):
    p[i] = 0.5*(p[i]+1)
d[0] = sum(p[0:k])
for i in range(1, n-k+1):
    d[i] = d[i-1] + p[i+k-1] -p[i-1]
print(max(d))
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
s = 0
for a in range(1,N+1):
  t = A.count(a)
  if t>= 2:
    s += (t-1)*t/2
  
for k in range(1,N+1):
  i = A[k-1]
  I = A.count(i)
  if I < 2:
    print(int(s))
  else:
    print(int(s - (I-1)))

### FIXED CODE ###

from collections import deque
N = int(input())
A = list(map(int,input().split()))
balls = [[] for _ in range(N+1)]
for i in range(N):
  balls[A[i]].append(i)
  
K = 0  
for i in range(N+1):
  if len(balls[i]) < 2:
    continue
  else:
    u = len(balls[i])
    K += int(u*(u-1)/2)
  
t = 0
q = deque()
for i in range(N):
  s = A[i]
  a = len(balls[s])
  if a >=2:
    d = a-1
  else:
    d = 0
  q.append(K-d)


while q:
  v = q.popleft()
  print(v)
### BUGGY CODE ###

#!/usr/bin/env python
import sys
N, M = map(int, input().split())
A = [int(input()) for i in range(M)]
m = 10**9+7
def Fib(n):
    a, b = 0, 1
    if n == 1:
        return a
    elif n == 2:
        return b
    else:
        for i in range(n-2):
            a, b = b, a + b
        return b

for i, a in enumerate(A[:-1]):
    if a+1 == A[i+1]:
        print(0)
        sys.exit()
ans = 1
s = 0
for i in range(N):
    if i in A:
        ans *= Fib(i-s+1)
        ans %= m
        s = i+1
ans *= Fib(N-s+2)
ans %= m 
print(ans)

### FIXED CODE ###

#!/usr/bin/env python
N, M = map(int, input().split())
m = 10**9+7
F = [0]*N
for _ in range(M):
    F[int(input())-1] = 1

a, b = 0, 1
for n in range(N):
    if F[n]:
        a, b = b, 0
    else:
        a, b = b, (a+b) % m
print(b)
### BUGGY CODE ###

N,K=map(int,input().split())
h=list(map(int,input().split()))

dp=[float("inf")]*N
dp[0]=0
for i in range(1,N):
  tmp=float("inf")
  for k in range(1,K+1):
    if i-k<0: break
    #dp[i]=min(dp[i],dp[i-k]+abs(h[i]-h[i-k]))
    tmp=min(tmp,dp[i-k]+abs(h[i]-h[i-k]))
  dp[i]=tmp

print(dp[N-1])

### FIXED CODE ###

import numpy as np
#https://yottagin.com/?p=1650

N,K=map(int,input().split())
h=list(map(int,input().split()))

#dp=[float("inf")]*N
#dp[0]=0
#dp=[0]
dp=np.zeros(N,dtype=int)
h=np.array(h)

for i in range(1,N):
  start=max(0,i-K)
  #start~i-1
  dp[i]=min(dp[start:i]+np.abs(h[i]-h[start:i]))
  #tmp=float("inf")
  #for k in range(1,K+1):
    #if i-k<0: break
    #dp[i]=min(dp[i],dp[i-k]+abs(h[i]-h[i-k]))
    #tmp=min(tmp,dp[i-k]+abs(h[i]-h[i-k]))
  #dp[i]=tmp
  #dp+=[tmp]

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

n = int(input())
a = [int(input()) for i in range(n)]
i = 1
count = 0

while True:
    i = a[i-1]
    count += 1
    if i == 1:
        print(-1)
        break
    elif i == 2:
        print(count)
        break

### FIXED CODE ###

n = int(input())
a = [int(input()) for i in range(n)]
i = 1
count = 0

while True:
    i = a[i-1]
    count += 1
    if i == 1 or count == n+1:
        print(-1)
        break
    elif i == 2:
        print(count)
        break
### BUGGY CODE ###

H, N = map(int, input().split())
magic = list()
for _ in range(N):
    magic.append(list(map(int, input().split())))

magic_min = [0 for _ in range(H+1)]
for i in range(H+1):
    if i != 0 and magic_min[i] == 0:
        continue
    for A, B in magic:
        Index = i + A
        value = magic_min[i] + B
        try:
            if magic_min[Index] == 0:
                magic_min[Index] = value
            elif value < magic_min[Index]:
                magic_min[Index] = value
        
        except:
            if magic_min[-1] == 0:
                magic_min[-1] = value
            elif value < magic_min[-1]:
                magic_min[-1] = value
                
print(magic_min[-1])

### FIXED CODE ###

H, N = map(int, input().split())
magic = list()
for _ in range(N):
    magic.append(list(map(int, input().split())))
 
magic_min = [0 for _ in range(H+1)]
for i in range(H+1):
    if i != 0 and magic_min[i] == 0:
        continue
    for A, B in magic:
        Index = i + A
        value = magic_min[i] + B
        try:
            if magic_min[Index] == 0:
                magic_min[Index] = value
            elif value < magic_min[Index]:
                magic_min[Index] = value
        
        except:
            if magic_min[-1] == 0:
                magic_min[-1] = value
            elif value < magic_min[-1]:
                magic_min[-1] = value
                
print(magic_min[-1])
### BUGGY CODE ###

import numpy as np
import sys
def input():
    return sys.stdin.readline()[:-1]

N, K, Q = map(int, input().split())

indexes = np.array(list(int(input()) for _ in range(Q)))-1

scores = np.array([K for _ in range(N)])

for i in indexes:
    scores[i] = scores[i]+1
    scores = scores-1

for j in scores:
    if j > 0:
        print('Yes')
    else:
        print('No')


### FIXED CODE ###

N, K, Q = map(int, input().split())

right_answers = list(int(input()) for _ in list(range(Q)))
indexes = [v-1 for v in right_answers]

scores = [K-Q for _ in range(N)]

for i in indexes:
    scores[i] = scores[i]+1

for j in scores:
    if j > 0:
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

n = int(input())
a = list(map(int, [input() for i in range(n)]))

maxa=max(a)

for i in range(n):
    if a[i]==maxa:
        list = a[:]
        list.pop(i)
        print(max(list))
    else:
        print(maxa)

### FIXED CODE ###

n = int(input())
a = list(map(int, [input() for i in range(n)]))

list=a[:]
list.sort(reverse=True)
max1 = list[0]
max2 = list[1]

for i in range(n):
    if a[i]==max1:
        print(max2)
    else:
        print(max1)
### BUGGY CODE ###

def countAC(s):
    counter = 0
    for i in range(len(s)):
        if i == len(s)-1:
            break
        if s[i] == 'A':
            if s[i+1] == 'C':
                counter += 1
    return counter



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

for i in range(Q):
    l,r = (int(_) for _ in input().split())
    s = S[l-1:r]
    print(countAC(s))


### FIXED CODE ###

def countAC(s):
    counter = 0
    index = [0]
    for i in range(1,N):
        if s[i-1] == 'A':
            if s[i] == 'C':
                counter += 1
                index.append(counter)
                continue
        index.append(counter)
    return index

N,Q = (int(_) for _ in input().split())
S = input()
SIndex = countAC(S)
out = 0
for i in range(Q):
    l,r = (int(_) for _ in input().split())
    print(SIndex[r-1] - SIndex[l-1])
### BUGGY CODE ###

s = list(input())
K = int(input())
character = '0abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyz'
limit = len(s) - 1

here = 0
while K:
    tmp = character.find(s[here])
    if tmp == 1 and here != limit:
        continue

    if tmp + K > 26 and here != limit:
        K -= 26 - tmp + 1
        s[here] = 'a'
        here += 1
    elif here == limit:
        K %= 26
        s[-1] = character[tmp + K]
        break
    else:
        here += 1
print(''.join(s))

### FIXED CODE ###

s = list(input())
K = int(input())
character = '0abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyz'
limit = len(s) - 1

here = 0
while K:
    tmp = character.find(s[here])
    if tmp == 1 and here != limit:
        here += 1
        continue

    if tmp + K > 26 and here != limit:
        K -= 26 - tmp + 1
        s[here] = 'a'
        here += 1
    elif here == limit:
        K %= 26
        s[-1] = character[tmp + K]
        break
    else:
        here += 1
print(''.join(s))
### BUGGY CODE ###

n=int(input())
a=list()
for i in range(n):
	s=sorted(input())
	a.append(s)
co=0  
for i in range(n-1):
  for j in range(i+1,n):
    if(a[i]==a[j]):
        co+=1
print(co)

### FIXED CODE ###

n = int(input())
b = list()
for _ in range(n):
    
    s = input()
    a = list()
    for i in range(len(s)):
        a.append(s[i])
    a.sort()
    s = ""
    s = s.join(a)
    
    b.append(s)
    
b.sort()
b.append("zzzzzzzzzzzzzzz")

ans = 0
cn  = 1
for i in range(0,len(b)-1):
    if(b[i]==b[i+1]):
        cn += 1
    else:
        ans += (cn*(cn-1))//2
        cn  = 1

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

import numpy as np
from numba import njit

@njit
def main(n,ma,mb,abc):
    inf=10**5
    cost=inf*np.ones((401,401))
    

    left=5*n//8
    right=n
    cnt=right-left

    for i in range(2**cnt):
        ta=0
        tb=0
        tc=0
        for j in range(cnt):
            if (i>>j)&1==1:
                a,b,c=abc[left+j]
                ta+=a
                tb+=b
                tc+=c
        
        cost[ta,tb]=min(cost[ta,tb],tc)
    
    ans=inf

    for i in range(1,401):
        targeta=ma*i
        targetb=mb*i

        for j in range(2**left):
            ta=0
            tb=0
            tc=0
            for k in range(left):
                if (j>>k)&1==1:
                    a,b,c=abc[k]
                    ta+=a
                    tb+=b
                    tc+=c
        
            ua=targeta-ta
            ub=targetb-tb

            if 0<=ua<=400 and 0<=ub<=400 and cost[ua,ub]!=inf:
                ans=min(ans,tc+cost[ua,ub])
    
    if ans==inf:
        return -1
    else:
        return int(ans)

n,ma,mb=map(int,input().split())
abc=np.array([list(map(int,input().split())) for _ in range(n)])
print(main(n,ma,mb,abc))

### FIXED CODE ###

n,ma,mb=map(int,input().split())
abc=[list(map(int,input().split())) for _ in range(n)]

wmax=400
inf=10**10
dp=[[[inf]*(wmax+1) for _ in range(wmax+1)] for _ in range(n+1)]
dp[0][0][0]=0

for i in range(n):
    a,b,c=abc[i]
    for j in range(wmax+1):
        for k in range(wmax+1):
            dp[i+1][j][k]=dp[i][j][k]

            if j>=a and k>=b:
                dp[i+1][j][k]=min(dp[i+1][j][k],dp[i][j-a][k-b]+c)

ans=inf

for j in range(1,wmax+1):
    for k in range(1,wmax+1):
        if dp[n][j][k]>=inf:
            continue

        if ma*k==mb*j:
            ans=min(ans,dp[n][j][k])

if ans==inf:
    print(-1)
else:
    print(ans)
### BUGGY CODE ###

n,p = list(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)
  exit()

def MS(i,s,pre):
  return (s*(10**i) +pre)%p
 
M = [0]*p
pre = 0
ans = 0
i = 0
for s in S[::-1]:
  pre = MS(i,int(s),pre)
  M[pre] += 1
  i += 1

M[0] += 1
for m in M:
  ans += (m*(m-1))//2
print(ans)

### FIXED CODE ###

n,p = list(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)
  exit()

def MS(i,s,pre):
  return (s*i +pre)%p
 
M = [0]*p
M[0] = 1
t = 1
now = 0
for i in S[::-1]:
    i = int(i)
    now += i*t
    now %= p
    M[now] += 1
    t = t*10%p

ans = sum(map(lambda m:(m*(m-1))//2, M))
print(ans)
### BUGGY CODE ###

def main():
    t = int(input())
    for _ in range(t):
        nn, aa, s, r, mm = int(input()), list(map(int, input().split())), input(), 0, []
        for ii in range(nn-1, -1, -1):
            ai = aa[ii]
            mm += [[(ai >> jj) & 1 for jj in range(64)]]
            n, i, j = r+1, 0, 0
            while i < n and j < 64:
                if mm[i][j] == 1 and mm[n-1][j] == 0:
                    i += 1
                    j += 1
                    continue
                if mm[i][j] == 0:
                    if mm[n-1][j] != 0:
                        for l in range(j, 64):
                            mm[i][l] ^= mm[n-1][l]
                    else:
                        j += 1
                        continue
                M2 = mm[i]
                for k in range(i+1, n):
                    M3 = mm[k][j]
                    mm[k][j] = 0
                    for l in range(j+1, 64):
                        mm[k][l] ^= M3*M2[l]
                i += 1
                j += 1
    
            if s[ii] == "0":
                if i > r:
                    r += 1
                else:
                    mm.pop()
            else:
                mm.pop()
                if i > r:
                    print(1)
                    break
        else:
            print(0)


main()


### FIXED CODE ###

def main():
    t = int(input())
    for _ in range(t):
        nn, aa, s, r, mm = int(input()), list(map(int, input().split())), input(), 0, []
        for ii in range(nn-1, -1, -1):
            ai = aa[ii]
            mm += [[(ai >> jj) & 1 for jj in range(64)]]
            n, i, j = r+1, 0, 0
            while i < n and j < 64:
                if mm[i][j] == 1 and mm[n-1][j] == 0:
                    i += 1
                    j += 1
                    continue
                if mm[i][j] == 0:
                    if mm[n-1][j] != 0:
                        for l in range(j, 64):
                            mm[i][l] ^= mm[n-1][l]
                    else:
                        j += 1
                        continue
                M2 = mm[i]
                for k in range(i+1, n):
                    M3 = mm[k][j]
                    mm[k][j] = 0
                    for l in range(j+1, 64):
                        mm[k][l] ^= M3*M2[l]
                i += 1
                j += 1
    
            if s[ii] == "0":
                if i > r:
                    r += 1
                else:
                    mm.pop()
            else:
                mm.pop()
                if i > r:
                    print(1)
                    break
        else:
            print(0)


main()
### BUGGY CODE ###

n = int(input())
a = [int(input()) for i in range(n)]
check = []
i = 0
while True:
    if i not in check:
        check.append(i)
        i = a[i]-1
    else:
        print(-1)
        break
    if i == 1:
        print(len(check))
        break
    
    


### FIXED CODE ###

n = int(input())
a = [None]
for j in range(n):
    a.append(int(input()))

i = 1
c = 0
r = [1]
while True:
    c += 1
    i = a[i]
    if i == 2:
        print(c)
        break
    if c > (10**5):
        print(-1)
        break