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

import sys
def input():
	return sys.stdin.readline()[:-1]
MOD = 998244353
n = int(input())
a = [int(input()) for _ in range(n)]
s = sum(a)
dp = [[0 for _ in range(s+1)] for _ in range(n+1)]
dp[0][0] = 1
for i in range(n):
	for j in range(s+1):
		dp[i+1][j] += dp[i][j] * 2
		dp[i+1][j] %= MOD
		if j+a[i] <= s:
			dp[i+1][j+a[i]] += dp[i][j]
			dp[i+1][j+a[i]] %= MOD
#print(*dp, sep="\n")
res = 0
for j in range(s+1):
	if j*2 >= s:
		res += dp[n][j] * 3
		res %= MOD

if s%2 == 0:
	dpp = [0 for _ in range(s+1)]
	dpp[0] = 1
	for i in range(n):
		for j in range(s-a[i], -1, -1):
			dpp[j+a[i]] += dpp[j]
			dpp[j+a[i]] %= MOD
	res -= dpp[s//2] * 3

print((pow(3, n, MOD) - res) % MOD)

### FIXED CODE ###

import sys
def input():
	return sys.stdin.readline()[:-1]
MOD = 998244353
n = int(input())
a = [int(input()) for _ in range(n)]
s = sum(a)
dp = [[0 for _ in range(s+1)] for _ in range(n+1)]
dp[0][0] = 1
for i in range(n):
	for j in range(s+1):
		dp[i+1][j] += dp[i][j] * 2
		dp[i+1][j] %= MOD
		if j+a[i] <= s:
			dp[i+1][j+a[i]] += dp[i][j]
			dp[i+1][j+a[i]] %= MOD
#print(*dp, sep="\n")
res = 0
for j in range(s+1):
	if j*2 >= s:
		res += dp[n][j] * 3
		res %= MOD

if s%2 == 0:
	dpp = [0 for _ in range(s+1)]
	dpp[0] = 1
	for i in range(n):
		for j in range(s-a[i], -1, -1):
			dpp[j+a[i]] += dpp[j]
			dpp[j+a[i]] %= MOD
	res -= dpp[s//2] * 3

print((pow(3, n, MOD) - res) % MOD)
### BUGGY CODE ###

from collections import deque
import sys
sys.setrecursionlimit(10**7)

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

g = [[int(i) for i in input().split()] for j in range(N-1)]
G = [[] for i in range(N)]
for i in range(N-1):
    a, b = g[i]
    G[a-1].append(b-1)
    G[b-1].append(a-1)

q = [[int(i) for i in input().split()] for j in range(Q)]
count = [0 for i in range(N)]
for i in range(Q):
    p, x = q[i]
    count[p-1] += x

def dfs(v, p):
    if p != -1:
        count[v] += count[p]
    for next_v in G[v]:
        if next_v == p: continue
        dfs(next_v, v)

dfs(0, -1)
for i in range(N):
    print(count[i], end=" ")

### FIXED CODE ###

from collections import deque

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

ab = [[int(i) for i in input().split()] for j in range(N-1)]
G = [[] for i in range(N)]
for i in range(N-1):
    a, b = ab[i]
    G[a-1].append(b-1)
    G[b-1].append(a-1)

q = [[int(i) for i in input().split()] for j in range(Q)]
count = [0 for i in range(N)]
for i in range(Q):
    p, x = q[i]
    count[p-1] += x

ls = deque([0])
seen = [0 for i in range(N)]
while len(ls) > 0:
    root = ls.popleft()
    seen[root] = 1

    for next_v in G[root]:
        if not seen[next_v]:
            count[next_v] += count[root]
            ls.append(next_v)

for i in range(N):
    print(count[i], end=" ")
### BUGGY CODE ###

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

l = [A[0]]
a = A[0] - 1
for _ in range(K):
    if A[a] not in l:
        l.append(A[a])
        a = A[a] - 1
    else:
        a = A[a]
        break
n = len(l)
b = 0
for i in range(n):
    if l[i] == a:
        del l[0:i]
        b = i
        break
T = len(l)
S = (K - b) % T
ans = l[S - 1]

print(ans)


### FIXED CODE ###

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

l = [A[0]]
s = {A[0]}
a = A[0] - 1
for _ in range(K):
    if A[a] not in s:
        l.append(A[a])
        s.add(A[a])
        a = A[a] - 1
    else:
        a = A[a]
        break
n = len(l)
b = 0
for i in range(n):
    if l[i] == a:
        del l[0:i]
        b = i
        break
T = len(l)
S = (K - b) % T
ans = l[S - 1]

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

S=input()
N=len(S)
A=[0]
for i in range(N):
    s=int(S[N-1-i:N])
    A.append(s%2019)
d={}
for i in range(len(A)):
    if not A[i] in d:
        d[A[i]]=1
    else:
        d[A[i]]+=1
ans=0
for k in d.keys():
    ans+=d[k]*(d[k]-1)//2
print(ans)

### FIXED CODE ###

S=input()
N=len(S)
A=[0]
for i in range(N):
    s=int(S[-1-i])
    A.append((A[-1]+(s*pow(10,i,2019)))%2019)
d={}
for i in range(len(A)):
    if not A[i] in d:
        d[A[i]]=1
    else:
        d[A[i]]+=1
ans=0
for k in d.keys():
    ans+=d[k]*(d[k]-1)//2
print(ans)
### BUGGY CODE ###

N=int(input())
S=str(input())
X=[0]*1000
for i in range(N-2):
  for j in range(i+1,N-1):
    for k in range(j+1,N):
      X[int(S[i])*100+int(S[j])*10+int(S[k])]=1
print(sum(X))

### FIXED CODE ###

N=int(input())
S=str(input())
X=[0]*1000
cnt=0
for i in range(10):
  a=S.find(str(i))
  if a==-1:
    continue
  else:
    for j in range(10):
      b=S[a+1:].find(str(j))
      if b==-1:
        continue
      else:
        for k in range(10):
          c=S[a+b+2:].find(str(k))
          if c==-1:
            continue
          else:
            cnt+=1
print(cnt)
### BUGGY CODE ###

def read_line(*types): return [f(a) for a, f in zip(input().split(), types)]

n, q = read_line(int, int)
s, = read_line(str)

m = [0 for _ in range(len(s) + 1)]

c = 0
for i in range(len(s)):
    if s[i:i+2] == 'AC':
        c += 1
    m[i + 1] = c

for i in range(q):
    l, r = read_line(int, int)
    l, r = l - 1, r - 1

    if c == 0:
        print(0)
        continue
    print(m[1:][r - 1] - m[l])


### FIXED CODE ###

def read_line(*types): return [f(a) for a, f in zip(input().split(), types)]

n, q = read_line(int, int)
s, = read_line(str)

m = [0 for _ in range(len(s) + 1)]

c = 0
for i in range(len(s)):
    if s[i:i+2] == 'AC':
        c += 1
    m[i + 1] = c

for i in range(q):
    l, r = read_line(int, int)

    if c == 0:
        print(0)
        continue
    print(m[r - 1] - m[l - 1])
### BUGGY CODE ###

N,K = map(int,input().split())
gcddic = {}
mod_n = (10**9+7)
for i in range(K,0,-1):
    x = pow((K//i),N)
    ll=2
    while(ll*i<=K):
        x -= gcddic[ll*(i)]
        ll += 1
    gcddic[i] = x
sumnation = 0
for i,l in gcddic.items():
    sumnation += i*l
print(sumnation%mod_n)

### FIXED CODE ###

N,K = map(int,input().split())
gcddic = {}
mod_n = (10**9+7)
for i in range(K,0,-1):
    x = pow((K//i),N,mod_n)
    ll=2
    while(ll*i<=K):
        x -= gcddic[ll*(i)]
        ll += 1
    gcddic[i] = x
sumnation = 0
for i,l in gcddic.items():
    sumnation += i*l
print(sumnation%mod_n)
### BUGGY CODE ###

import math

a,b = tuple(map(int,input().split(" ")))
ans = 1
for i in range(a,b+1):
    ans *= i

if a>0:
    print("Positive")
elif a<0 and b>0:
    print("Zero")
elif a%2==0 and b%2==0 or a%2==1 and b%2==1:
    print("Negative")
else:
    print("Positive")


### FIXED CODE ###

import math

a,b = tuple(map(int,input().split(" ")))
if a>0:
    print("Positive")
elif a<0 and b>0:
    print("Zero")
elif a%2==0 and b%2==0 or a%2==1 and b%2==1:
    print("Negative")
else:
    print("Positive")
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
INF = float("inf")


def solve(N: int, T: int, A: "List[int]", B: "List[int]"):

    # DP1
    # 1からi番目の料理でj分以内に完食できる美味しさの合計の最大値
    DP1 = [[0 for _ in range(T+1)] for __ in range(N+1)]
    for i in range(1, N+1):
        for j in range(1, T+1):
            if j-A[i-1] >= 0:
                DP1[i][j] = max(DP1[i][j], DP1[i-1][j-A[i-1]]+B[i-1])
            DP1[i][j] = max(DP1[i][j], DP1[i-1][j], DP1[i][j-1])

    # DP2
    # i番目からN番目の料理でj分以内に完食できる美味しさの合計の最大値
    DP2 = [[0 for _ in range(T+1)] for __ in range(N+2)]
    for i in range(N, 0, -1):
        for j in range(1, T+1):
            if j-A[i-1] >= 0:
                DP2[i][j] = max(DP2[i][j], DP2[i+1][j-A[i-1]]+B[i-1])
            DP2[i][j] = max(DP2[i][j], DP2[i+1][j], DP2[i][j-1])

    # i番目以外の料理でT-1分以内に完食できる美味しさの合計の最大値
    ans = 0
    for i in range(1, N+1):
        bns = 0
        for j in range(T):
            bns = max(bns, DP1[i-1][j] + DP2[i+1][T-j-1])
        ans = max(ans, bns+B[i-1])
    print(ans)

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    T = int(next(tokens))  # type: int
    A = [int()] * (N)  # type: "List[int]"
    B = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        A[i] = int(next(tokens))
        B[i] = int(next(tokens))
    solve(N, T, A, B)


if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
INF = float("inf")


def solve(N: int, T: int, A: "List[int]", B: "List[int]"):

    # DP1
    # 1からi番目の料理でj分以内に完食できる美味しさの合計の最大値
    DP1 = [[0 for _ in range(T+1)] for __ in range(N+1)]
    for i in range(1, N+1):
        for j in range(1, T+1):
            if j-A[i-1] >= 0:
                DP1[i][j] = max(DP1[i][j], DP1[i-1][j-A[i-1]]+B[i-1])
            DP1[i][j] = max(DP1[i][j], DP1[i-1][j], DP1[i][j-1])

    # DP2
    # i番目からN番目の料理でj分以内に完食できる美味しさの合計の最大値
    DP2 = [[0 for _ in range(T+1)] for __ in range(N+2)]
    for i in range(N, 0, -1):
        for j in range(1, T+1):
            if j-A[i-1] >= 0:
                DP2[i][j] = max(DP2[i][j], DP2[i+1][j-A[i-1]]+B[i-1])
            DP2[i][j] = max(DP2[i][j], DP2[i+1][j], DP2[i][j-1])

    # i番目以外の料理でT-1分以内に完食できる美味しさの合計の最大値
    ans = 0
    for i in range(1, N+1):
        bns = 0
        for j in range(T):
            bns = max(bns, DP1[i-1][j] + DP2[i+1][T-j-1])
        ans = max(ans, bns+B[i-1])
    print(ans)

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    T = int(next(tokens))  # type: int
    A = [int()] * (N)  # type: "List[int]"
    B = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        A[i] = int(next(tokens))
        B[i] = int(next(tokens))
    solve(N, T, A, B)


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

import sys
sys.setrecursionlimit(10 ** 7)

N,Q = map(int,input().split())
AB = [[int(x) for x in input().split()] for _ in range(N-1)]
PX = [[int(x) for x in input().split()] for _ in range(Q)]

graph = [[] for _ in range(N+1)]
for a,b in AB:
    graph[a].append(b)
    graph[b].append(a)

value = [0] * (N+1)
for p,x in PX:
    value[p] += x

def dfs(v,parent,add):
    value[v] += add
    for x in graph[v]:
        if x == parent:
            continue
        dfs(x,v,value[v])

dfs(1,0,0)

answer = ' '.join(map(str,value[1:]))
print(answer)


### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

N,Q = map(int,input().split())
AB = [[int(x) for x in input().split()] for _ in range(N-1)]
PX = [[int(x) for x in input().split()] for _ in range(Q)]

graph = [[] for _ in range(N+1)]
for a,b in AB:
    graph[a].append(b)
    graph[b].append(a)

value = [0] * (N+1)
for p,x in PX:
    value[p] += x

def dfs(v,parent,add):
    value[v] += add
    for x in graph[v]:
        if x == parent:
            continue
        dfs(x,v,value[v])

dfs(1,0,0)

answer = ' '.join(map(str,value[1:]))
print(answer)
### BUGGY CODE ###

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

cnt = 0

for i in ints:
    clr = [i % j == 0 for j in ints]
    if clr.count(True) == 1:
        cnt += 1

print(cnt)



### FIXED CODE ###

n = int(input())
ints = list(map(int, input().split()))
m = max(ints)
x = [0] * m
cnt = 0

for i in ints:
    if x[i-1] >= 2:
        continue
    for j in range(m // i):

        x[i * (j + 1) - 1] += 1

for i in ints:
    if x[i - 1] == 1:
        cnt += 1

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

N = int(input())
mx = 3503
found = False
for i in range(1, mx):
    for j in range(1, mx):
        num = N*i*j
        den = (i*j*4 - N*i - N*j)
        if den == 0:
            continue
        if num%den == 0 and num//den > 0 and num//den < mx:
            print(i,j,num//den)
            found = True
            break
    if found:
        break

### FIXED CODE ###

N = int(input())
mx = 3503
found = False
for i in range(1, mx):
    for j in range(1, mx):
        if i*j*4 % N != 0:
            continue
        den = ((i*j*4)//N) - i - j
        num = i*j
        if den == 0:
            continue
        if num%den == 0 and num//den > 0 and num//den < mx:
            print(i,j,num//den)
            found = True
            break
    if found:
        break
### BUGGY CODE ###

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

A = sorted(A)
mod = 10**9+7
setA = [0]*N
setA[-1] = A[-1]

for i in range(N):
  if A[-1]%A[i] != 0:
    setA[i] = A[i]
setA = [s for s in setA if s != 0]


import fractions
from functools import reduce

 
def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)
 
def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)
 
def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)
 
 
l = lcm(*setA)
B = 0

for i in range(N):
  B += l//A[i]%mod
B %= mod
print(B)

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
mod = 10**9+7

import fractions
from functools import reduce

def gcd(x,y):
  if x == 0:
    return y
  else:
    return gcd(y-x*(y//x),x)
 

def lcm(x, y):
    return (x*y)//gcd(x,y)
    
l = 1
B = 0

for i in range(N):
  l = lcm(l,A[i])
for i in range(N):
  B += l//A[i]
B %= mod

print(B)
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
for i in range(n):
    c=0
    for e in a:
        if i+1==e:
            c+=1
    print(c)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
b=[]
for i in range(n):
    b.append(0)
for i in a:
    b[i-1]+=1
for i in b:
    print(i)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

n = int(input())
A = [0]*n
A[0] = int(input())
for i in range(1,n):
    a = int(input())
    if a in A:
        A.remove(a)
    else:
        A[i] = a
print(len(set(A))-1)

### FIXED CODE ###

import collections
import sys
input = sys.stdin.readline

n = int(input())
a = [0]*n
ans = 0
for i in range(n):
    a[i] = int(input())
count_a = collections.Counter(a).most_common()
for i in range(len(count_a)):
    if count_a[i][1]%2 != 0:
        ans += 1
print(ans)
### BUGGY CODE ###

import sys
readline = sys.stdin.readline

def main():
    N, K = map(int, readline().rstrip().split())
    X = list(map(int, readline().rstrip().split()))
    len_m = len([x for x in X if x < 0])
    len_p = len([x for x in X if x > 0])
    ans = 10**10
    idx = max(0, len_m-K)
    s = [0] + X[idx:idx+K-1]
    for i in range(max(0, len_m-K), min(len_m+K, N-K+1)):
        s = s[1:] + [X[i+K-1]]
        if len(s) != K:
            continue
        if s[0] < 0 and s[-1] > 0:
            c = min(abs(s[0]) * 2 + s[-1], abs(s[0]) + s[-1] * 2)
        else:
            c = max(abs(s[0]), abs(s[-1]))
        ans = min(ans, c)

    print(ans)


if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
readline = sys.stdin.readline

def main():
    N, K = map(int, readline().rstrip().split())
    X = list(map(int, readline().rstrip().split()))
    len_m = len([x for x in X if x < 0])
    len_p = len([x for x in X if x > 0])
    ans = 10**10
    idx = max(0, len_m-K)
    s = [0] + X[idx:idx+K-1]
    for i in range(max(0, len_m-K), min(len_m+K, N-K+1)):
        s.pop(0)
        s.append(X[i+K-1])
        if len(s) != K:
            continue
        if s[0] < 0 and s[-1] > 0:
            c = min(abs(s[0]) * 2 + s[-1], abs(s[0]) + s[-1] * 2)
        else:
            c = max(abs(s[0]), abs(s[-1]))
        ans = min(ans, c)

    print(ans)


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

N = int(input())
S = input()
out = 0
for i in range(0,N):
    for j in range(i,N):
        for k in range(j,N):
            if S[i] != S[j] and S[j] != S[k] and S[i] != S[k]:
                if j-i != k-j:
                    out+=1;

print(out)


### FIXED CODE ###

N = int(input())
S = input()
r,g,b = S.count('R'),S.count('G'),S.count('B')
#rgbでr,g,bがすべて異なる組み合わせ数
total = r*g*b
# そこからj-i=k-jの組み合わせを引く
for i in range(0,N-2):
    for j in range(i+1,N-1):
        k = 2*j-i
        if k >= N: break;
        if S[i] != S[j] and S[j] != S[k] and S[k] != S[i]:
            total-=1
# flg = [[[0 for i in range(N)] for j in range(N)] for k in range(N)]

print(total)
### BUGGY CODE ###

n = int(input())

count=0

for i in range(n):
    count+=i

print(count)

### FIXED CODE ###

n = int(input())

n-=1

print(n*(n+1)//2)
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
import math
import decimal
import itertools
from itertools import product
from functools import reduce
def input():
    return sys.stdin.readline()[:-1]
def gcd(*numbers):
    return reduce(math.gcd, numbers)
def lcm_base(x, y):
    return (x * y) // math.gcd(x, y)
def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)
def sort_zip(a:list, b:list):
    z = zip(a, b)
    z = sorted(z)
    a, b = zip(*z)
    a = list(a)
    b = list(b)
    return a, b
def ceil(x):
    return math.ceil(x)
def floor(x):
    return math.floor(x)

def main():
    mod = 998244353
    N, K = map(int, input().split())
    L = [0] * K
    R = [0] * K
    for i in range(K):
        L[i], R[i] = map(int, input().split())

    S = set()
    for i in range(K):
        for j in range(L[i], R[i] + 1):
            S.add(j)

    dp = [0] * N
    dp[0] = 1
    for i in range(1, N):
        for s in S:
            if i - s >= 0:
                dp[i] += dp[i - s]
    print(dp[N - 1] % mod)


if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
import math
import decimal
import itertools
from itertools import product
from functools import reduce
def input():
    return sys.stdin.readline()[:-1]
def gcd(*numbers):
    return reduce(math.gcd, numbers)
def lcm_base(x, y):
    return (x * y) // math.gcd(x, y)
def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)
def sort_zip(a:list, b:list):
    z = zip(a, b)
    z = sorted(z)
    a, b = zip(*z)
    a = list(a)
    b = list(b)
    return a, b
def ceil(x):
    return math.ceil(x)
def floor(x):
    return math.floor(x)


def main():
    MOD = 998244353
    N, K = map(int, input().split())
    L = [0] * K
    R = [0] * K
    for i in range(K):
        L[i], R[i] = map(int, input().split())

    dp = [0] * (N + 1)
    dpsum = [0] * (N + 1)
    dp[1] = 1
    dpsum[1] = 1
    for i in range(2, N + 1):
        for j in range(K):
            li = i - R[j]
            li = max(li, 1)
            ri = i - L[j]
            if ri < 0:
                continue
            dp[i] += (dpsum[ri] - dpsum[li - 1]) % MOD
        dpsum[i] += (dpsum[i - 1] + dp[i]) % MOD
    print(dp[N] % MOD)


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

n = int(input())
l = list(map(int, input().split()))
ans = 0

for i in range(n-2):
  for j in range(i+1, n-1):
    #print("i: "+str(i)+"  j: "+str(j))
    #print(max(l[i], l[j])-min(l[i], l[j]))
    #print(l[i]+l[j])
    #print(list(filter(lambda x: max(l[i], l[j])-min(l[i], l[j])<x<l[i]+l[j], l[j+1:])))
    ans +=  len(list(filter(lambda x: max(l[i], l[j])-min(l[i], l[j])<x<l[i]+l[j], l[j+1:])))
    
print(ans)

### FIXED CODE ###

from bisect import bisect_left

n = int(input())
l = list(map(int, input().split()))
l.sort()
ans = 0

for i in range(n-2):
  for j in range(i+1, n-1):
    #print("i: "+str(i)+"  j: "+str(j))
    #print(max(l[i], l[j])-min(l[i], l[j]))
    #print(l[i]+l[j])
    #print(list(filter(lambda x: max(l[i], l[j])-min(l[i], l[j])<x<l[i]+l[j], l[j+1:])))
    #temp1 = bisect_left(l[j+1:], l[j]-l[i])
    #temp2 = bisect_left(l[j+1:], l[j]+l[i])
    #print(temp1)
    #print(temp2)
    ans += bisect_left(l[j+1:], l[j]+l[i])
    
print(ans)
### BUGGY CODE ###

# -*- coding: utf-8 -*-

import sys
from collections import deque

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N = INT()
A = [deque()]
for i in range(N):
    A.append(deque(LIST()))

cnt = N*(N-1)//2
day = 0
while cnt > 0:
    prev = cnt
    skip = [False] * (N+1)
    for i in range(1, N+1):
        if len(A[i]) and not skip[i]:
            a = A[i][0]
            if len(A[a]) and not skip[a]:
                b = A[a][0]
                if i == b:
                    A[i].popleft()
                    A[a].popleft()
                    cnt -= 1
                    skip[i] = skip[a] = True
    if prev == cnt:
        print(-1)
        exit()
    day += 1
    if day > 200000:
        print(N*(N-1)//2)
        exit()
print(day)


### FIXED CODE ###

# -*- coding: utf-8 -*-

import sys
import time
from collections import deque

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N = INT()
A = [deque()]
for i in range(N):
    A.append(deque(LIST()))

start = time.time()

cnt = N*(N-1)//2
day = 0
while cnt > 0:
    prev = cnt
    skip = [False] * (N+1)
    for i in range(1, N+1):
        if len(A[i]) and not skip[i]:
            a = A[i][0]
            if len(A[a]) and not skip[a]:
                b = A[a][0]
                if i == b:
                    A[i].popleft()
                    A[a].popleft()
                    cnt -= 1
                    skip[i] = skip[a] = True
    if prev == cnt:
        print(-1)
        exit()
    day += 1

    elapsed_time = time.time() - start
    if elapsed_time > 1:
        print(N*(N-1)//2)
        exit()
print(day)
### BUGGY CODE ###

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

ans = a[0]
for i in range(1,n):
    ans *= a[i]
if ans > 10**18:
    print(-1)
else:
    print(ans)

### FIXED CODE ###

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

ans = a[0]
if a.count(0) == 0:
    for i in range(1,n):
        ans *= a[i]
        if ans > 10**18:
            ans = -1
            break
else:
    ans = 0
print(ans)
### BUGGY CODE ###

import collections
N = int(input())
A = list(map(int, input().split()))
A = sorted(A)
c = collections.Counter(A)
cnt = 0
max = int(10e5+1)
l = [0] * (max+1)
for n in A:
    for j in range(n, max+1, n):
        l[j] += 1
for n in A:
    if c[n] > 1:
        continue
    if l[n] == 1:
        cnt += 1
print(cnt)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
cnt = 0
max = int(10e5+1)
l = [0] * (max+1)
for n in A:
    if l[n] != 0:
        l[n] = 2
        continue
    for j in range(n, max+1, n):
        l[j] += 1
for n in A:
    if l[n] == 1:
        cnt += 1
print(cnt)
### BUGGY CODE ###

def main():
    n,q = map(int, input().split())
    S = list(input())
    array = [list(map(int,input().split())) for _ in range(q)]

    for i in range(q):
        count = 0
        S_temp = S[array[i][0]-1:array[i][1]]
        for j in range(len(S_temp)):
            if j == len(S_temp)-1:
                break
            if S_temp[j] == 'A':
                if S_temp[j+1] == 'C':
                    count += 1
        print(count)


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    n,q = map(int, input().split())
    S = input()
    N = [0]*(n+1)

    for i in range(n):
        N[i+1] += N[i]
        if S[i:i+2] == 'AC':
            N[i+1] += 1
    for i in range(q):
        l,r = map(int,input().split())
        print(N[r-1]-N[l-1])


if __name__ == '__main__':
    main()