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

from collections import deque

N = int(input())
A = list(map(int, input().split()))
que = deque([0]*N)
bn = 0
for i in range(N, 0, -1):
    nn = 0
    for j in range(2*i, N+1, i):
        nn += que[j-1]

    if nn % 2 != A[i-1]:
        que[i-1] = 1

M = sum(que)
print(sum(que))
if M != 0:
    ans = []
    flg = False
    for i, n in enumerate(que):
        if flg:
            print(' ', end='')
        if n == 1:
            print(i+1, end='')
        flg = True

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
num_l = [0]*N
bn = 0
for i in range(N, 0, -1):
    nn = 0
    for j in range(2*i, N+1, i):
        nn += num_l[j-1]

    if nn % 2 != A[i-1]:
        num_l[i-1] = 1

M = sum(num_l)
print(M)
if M != 0:
    ans = []
    flg = False
    for i, n in enumerate(num_l):
        if flg:
            print(' ', end='')
        if n == 1:
            print(i+1, end='')
        flg = True
### BUGGY CODE ###

n,q=list(map(int,input().split()))
s=input()
lr=[list(map(int,input().split())) for i in range(q)]
for l,r in lr:
    print(len(s[l-1:r].split("AC"))-1)

### FIXED CODE ###

n, q = map(int, input().split())
s = input()
t = [0] * (n + 1)
for i in range(n):
    t[i + 1] = (1 if s[i:i + 2] == "AC" else 0) + t[i]
for i in range(q):
    l, r = list(map(int, input().split()))
    print(t[r - 1] - t[l - 1])
### BUGGY CODE ###

# -*- coding: utf-8 -*-
n, k = map(int,input().split())
p = [int(i) for i in input().split()]

ans = 0
tmp = 0
for i in range(k):
    ans += sum([i for i in range(1, p[i] + 1)]) / p[i]
    tmp = ans
#print(ans)
for i in range(n - k):
    tmp = tmp + (sum([i for i in range(1, p[i + k] + 1)]) / p[i + k]) - (sum([i for i in range(1, p[i] + 1)]) / p[i])
    #print(p[i], p[i + k], tmp)
    #print(p[i], sum([i for i in range(1, p[i] + 1)]) / p[i])
    #print(p[i + k], sum([i for i in range(1, p[i + k] + 1)]) / p[i + k])
    if tmp > ans:
        ans = tmp
print(ans)


### FIXED CODE ###

# -*- coding: utf-8 -*-
n, k = map(int,input().split())
p = [int(i) for i in input().split()]

kitai = []
for i in range(n):
    kitai.append((1 + p[i]) / 2)

ans = 0
tmp = 0
for i in range(k):
    tmp += kitai[i]
ans = tmp
for i in range(n - k):
    tmp = tmp - kitai[i] + kitai[i + k]
    if ans < tmp:
        ans = tmp
print(ans)
### BUGGY CODE ###


#１回のクエリで半分に空席がある場所を絞る
end = int(input())
print(0, flush=True)
S = input().rstrip()[0]
if S == 'V':
    exit()
start = 0
cur = S
for _ in range(19):
    target = start + max(2, (end - start) // 4 * 2)
    print(target, flush=True)
    s = input().rstrip()[0]
    if s == 'V':
        exit()
    if cur != s:
        end = target
    else:
        start = target
print(start + 1, flush=True)
s = input().rstrip()[0]
if s == 'V':
    exit()
else:
    print(start + 2, flush=True):
    exit()
#24


### FIXED CODE ###

N = int(input())

def ask(n):
    print(n, flush=True)
    resp = input().rstrip()[0]
    if resp == 'V':
        exit()
    return resp

def condition(L,R,resp_L,resp_R):
    if (R-L)&1:
        return resp_L == resp_R
    else:
        return resp_L != resp_R

resp = ask(0)

L = 0
R = N
resp_L = resp
resp_R = resp
for _ in range(19):
    M = (L + R) // 2
    resp_M = ask(M)
    if condition(L,M,resp_L,resp_M):
        R,resp_R = M,resp_M
    else:
        L,resp_L = M,resp_M
### BUGGY CODE ###

N,M,K = map(int,input().split())
d = [[float('inf') for _ in range(N)] for _ in range(N)]
for i in range(M):
  a,b = map(int,input().split())
  a -= 1
  b -= 1
  d[a][b] = 1
  d[b][a] = 1
for i in range(N):
  d[i][i] = 0
for k in range(N):
  for i in range(N):
    for j in range(N):
      d[i][j] = min(d[i][j],d[i][k]+d[k][j])
for i in range(K):
  c,e = map(int,input().split())
  c -= 1
  e -= 1
  d[c][e] = float('inf')
  d[e][c] = float('inf')
ans =[]
for i in range(N):
  cnt = 0
  for j in range(N):
    if i != j and d[i][j] > 1 and d[i][j] != float('inf'):
      cnt += 1
  ans.append(cnt)
print(*ans)

                                      


### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 9)

N,M,K = map(int,input().split())
AB = [list(map(int,input().split())) for _ in range(M)]
CD = [list(map(int,input().split())) for _ in range(K)]

V = [[] for _ in range(N)]
for a,b in AB:
  a -= 1
  b -= 1
  V[a].append(b)
  V[b].append(a)
# print(V)

L = [0 for _ in range(N)]
def dfs(u,l):
  L[u] = l
  for t in V[u]:
    if L[t] == 0:
      dfs(t,l)

l = 1
for i in range(N):
  if L[i] == 0:
    dfs(i,l)
    l += 1
#print(L)
C = {}
for ll in L:
  if ll in C:
    C[ll] += 1
  else:
    C[ll] = 1
#print(C)
ans = [C[L[i]]-1 for i in range(N)]
for a,b in AB:
  a -= 1
  b -= 1
  ans[a] -= 1
  ans[b] -= 1
for c,d in CD:
  c -= 1
  d -= 1
  if L[c] == L[d]:
    ans[c] -= 1
    ans[d] -= 1
print(*ans)
### BUGGY CODE ###

N = int(input())
 
for i in range(1,N+1):
  count = 0
  if i < 6:
    print('0')
  elif i == 6:
    print('1')
  else:
    for j in range(1,101):
      for k in range(1,101):
        for l in range(1,101):
          if (j**2+k**2+l**2+j*k+k*l+l*j)==i:
            count += 1
        
    print(count)

### FIXED CODE ###

N = int(input())
l = [0]*N

for x in range(1,101):
  for y in range(1,101):
    for z in range(1,101):
      if (x**2+y**2+z**2+x*y+y*z+z*x)<=N:
        l[x**2+y**2+z**2+x*y+y*z+z*x-1]+=1

for i in l:
  print(i)
### BUGGY CODE ###

import itertools
n = int(input())
a = list(map(int,input().split()))
tmp = 0
#ans = [0]*n
for i in range(n):
    tmp = a[i]
    a[i] = 0
    count = 0
    for it in itertools.combinations(a,2):
        if it[0] == it[1]:
            count += 1
    print(count)
    a[i] = tmp

### FIXED CODE ###

from collections import Counter
N = int(input())
An = list(map(int, input().split()))
counter = Counter(An)
cnt = 0
for c in counter.values():
    cnt += c * (c-1) // 2
for a in An:
    print(cnt - (counter[a] - 1))
### BUGGY CODE ###

N = int(input())
D = [int(i) for i in input().split()]
M = int(input())
T = [int(i) for i in input().split()]

for i in T:
    if i not in D:
        print('NO')
        exit()
    else:
        D.remove(i)

print('YES')


### FIXED CODE ###

from collections import Counter

N = int(input())
D = [int(i) for i in input().split()]
M = int(input())
T = [int(i) for i in input().split()]

d = Counter(D)
t = Counter(T)
d_key = list(d.keys())
t_key = list(t.keys())

p = len(d_key)
d_key += t_key
q = set(d_key)

if p != len(q):
    print('NO')
    exit()

for i in t_key:
    if t[i] > d[i]:
        print('NO')
        exit()

print('YES')
### BUGGY CODE ###

import heapq
def SME():
    A = [[x,i] for i,x in enumerate(Whole)]
    heapq.heapify(A)
    C = set([i for i in range(N)])
    D = set([])
    if N < 5*(10**4) :
        parameter = 0.8
    else :
        parameter = 0.997
    count = 0
    ANS = [None] * N
    for j in range(N) :
        a = heapq.heappop(A)
        for i,x in enumerate(ANS[a[1]:a[1]+L]):
            if x : continue
            else :
                ANS[a[1]+i] = a[0]
                D.add(a[1]+i)
                count += 1
        if count > N * parameter : break
    for i in C.difference(D):
        if i < L : ANS[i] = min(Whole[:i+1])
        else : ANS[i] = min(Whole[i+1-L:i+1])
    return ANS

[N,L] = [int(x) for x in input().split()]
Whole = [int(x) for x in input().split()]
ANS = SME()
for i in ANS[L-1:-1]:print(i, end=" ")
print(ANS[-1])

### FIXED CODE ###

def ascend(a,b):
    mini = min(A[a:a+L])
    ans[a] = mini
    for i in range(a+1,b):
        if A[i+L-1] <= mini : mini = A[i+L-1]
        elif A[i-1] == mini : mini = min(A[i:i+L])
        ans[i] = mini

def descend(a,b):
    mini = min(A[b-1:b+L-1])
    ans[b-1] = mini
    for i in range(b-2,a-1,-1):
        if A[i] <= mini : mini = A[i]
        elif A[i+L] == mini: mini = min(A[i:i+L])
        ans[i] = mini
    
[N,L] = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
ans = [None]*(N-L+1)
count = 0;
if N > 10 ** 4:
    for i in range(100):
        if A[i+1] > A[i] : count += 1
    if count > 80 : descend(0, N-L+1)
    else : ascend(0,N-L+1)
else :
    ascend(0, N-L+1)
for i in ans[:-1] : print(i, end=" ")
print(ans[-1])
### BUGGY CODE ###

from itertools import combinations

n = int(input())
l = list(map(int, input().split()))
answer = 0
for a, b, c in combinations(l, 3):
    if a < b + c and b < a + c and c < a + b:
        answer += 1
print(answer)


### FIXED CODE ###

from bisect import bisect_left

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

for i in range(n - 2):
    for j in range(i + 1, n - 1):
        lij = l[i] + l[j]
        r = bisect_left(l, lij)
        answer += max(0, r - j - 1)
        
print(answer)
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10000000)
INF = 1<<32

def solve(N: int):
    # from functools import lru_cache
    # # abc154を参考にメモ化で出すとTLE
    # @lru_cache(None)
    # def f(n: int):
    #     if 0 <= n <=5:
    #         return n
    #     elif 6 <= n < 10:
    #         return 10-n+1

    #     q, r = divmod(n, 10)
    #     # print(q, r)
    #     return min(
    #         f(q)+r,
    #         f(q+1)+10-r
    #     )
    # print(f(N))

    # N=36を考える
    l = list(map(int, list(str(N))))
    dp = 0,1
    for i in l:
        # a = f(3), f(36)
        a = min(dp[0]+i, dp[1]+10-i)
        # b = f(4), f(40)
        b = min(dp[0]+i+1, dp[1]+10-(i+1))
        dp = a, b

    print(dp[0])
    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
    solve(N)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
# sys.setrecursionlimit(10000000)
# INF = 1<<32

def solve(N: "List[int]"):
    # N=36を考える
    # l = list(map(int, list(str(N))))
    dp = 0,1
    for i in N:
        # a = f(3), f(36)
        a = min(dp[0]+i, dp[1]+10-i)
        # b = f(4), f(40)
        b = min(dp[0]+i+1, dp[1]+10-(i+1))
        dp = a, b

    print(dp[0])
    return



def main():
    stdin = open(0)
    N = [int(x) for x in stdin.read().rstrip()]
    solve(N)

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

import numpy as np
import sys

next(sys.stdin)
n = np.array(list(map(int, next(sys.stdin).split())))
j = np.arange(len(n)) + 1

while True:
    if np.all(n == 0):
        print('YES')
        break

    k = n.argmin()
    n = np.hstack((n[k:], n[:k]))

    d = ((n[1:] - n[0]) // (j[1:] - j[0])).min()
    p = (n // j).min()
    t = min(d + 1, p)

    if t > 0:
        n -= j * t
    else:
        print('NO')
        break


### FIXED CODE ###

import numpy as np
import sys

n = int(next(sys.stdin))
a = np.array(list(map(int, next(sys.stdin).split())))
j = np.arange(n) + 1

if np.any(a.sum() % j.sum() > 0):
    print('NO')
    exit()

s = a.sum() // j.sum()
k = s - (a[1:] - a[:-1])
if np.all(k >= 0) and np.all(k % n == 0):
    print('YES')
else:
    print('NO')
### BUGGY CODE ###

import collections
X = int(input())
dp = {}
dp[0] = 0

for i in range(1,X+1):
    dp_ = dp.copy()
    for key in dp.keys():
        if not key+i in dp.keys(): dp_[key+i] = i
        else: dp_[key+i] = min(dp_[key+i], i)

        if not key-i in dp.keys(): dp_[key-i] = i
        else: dp_[key-i] = min(dp_[key-i],i)
    dp = dp_
ans = dp[X]
print(ans)



### FIXED CODE ###

import math
X = int(input())
n =  math.ceil((math.sqrt(1+8*X) - 1)/2)
ans = n
print(ans)
### BUGGY CODE ###

import statistics

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

ans = -1
for i in range(N-K+1):
    sum = 0
    for j in range(K):
        tmp = P[i+j]
        sum += tmp - 0.5*(tmp-1)
    
    ans = max(ans, sum)

print(ans)

### FIXED CODE ###

N, K = map(int, input().split())
P = list(map(int, input().split()))
memo = sum(P[:K])
ans = memo

for i in range(K, N):
    memo = memo - P[i-K] + P[i]
    ans = max(ans, memo)

print(K-1+((ans-K+1) - 0.5*((ans-K+1)-1)))
### BUGGY CODE ###

ni = lambda: int(input())
nm = lambda: map(int, input().split())
nl = lambda: list(map(int, input().split()))

n, m = nm()

a = nl()

for i in range(m):
    b, c = nm()
    a += [c] * b

print(sum(sorted(a, reverse=True)[:n]))

### FIXED CODE ###

ni = lambda: int(input())
nm = lambda: map(int, input().split())
nl = lambda: list(map(int, input().split()))

n, m = nm()

a = sorted(nl())

pos = 0

changer = []

for i in range(m):
    b, c = nm()
    changer.append((c, b))

changer = sorted(changer)[::-1]


for i in range(m):

    c = changer[i]
    for j in range(c[1]):
        while pos < n:
            if a[pos] < c[0]:
                a[pos] = c[0]
                break
            pos += 1
    if pos >= n:
        break

print(sum(a))
### BUGGY CODE ###

S = input()
T = input()

out_str = "Yes"
well_known_indexes = []
for i in range(len(S)) :
	if(i in well_known_indexes) :
		continue

	indexes_s = [n for n, x in enumerate(list(S)) if x == S[i]]
	indexes_t = [n for n, x in enumerate(list(T)) if x == T[i]]
	if (indexes_s == indexes_t) :
		well_known_indexes.extend(indexes_s)
		continue
	out_str = "No"
	break

print(out_str)

### FIXED CODE ###

S = input()
T = input()

out_str = "Yes"

indexes_s_all = []
indexes_t_all = []
for i in range(26) :
	c = chr(ord('a') + i)
	indexes_s = [n for n, x in enumerate(list(S)) if x == c]
	indexes_t = [n for n, x in enumerate(list(T)) if x == c]
	indexes_s_all.append(indexes_s)
	indexes_t_all.append(indexes_t)

indexes_s_all.sort()
indexes_t_all.sort()
if (indexes_s_all == indexes_t_all) :
	print("Yes")
else :
	print("No")
### BUGGY CODE ###

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

answer = 1
for Ai in A:
    answer *= Ai

if answer > 10 ** 18:
    answer = -1

print(answer)


### FIXED CODE ###

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

haz_zero = 0 in A
if haz_zero:
    print(0)
    exit()

answer = 1
for Ai in A:
    answer *= Ai
    if answer > 10 ** 18:
        answer = -1
        break

print(answer)
### BUGGY CODE ###

N = int(input())
S = input()
for w in 'abcdefghijklmnopqrstuvwxyz':
  if S.find(w) != -1:
    while S.count(w) != 1:
      if S[S.find(w) + 1] == w:
        S.replace(w + w,w)
print(len(S))

### FIXED CODE ###

N = int(input())
S = input()
ans = 1
for i in range(N):
  if i <= len(S)-2:
    if S[i] !=S[i+1]:
      ans = ans + 1
print(ans)
### BUGGY CODE ###


n = int(input())
p_list = list(map(int, input().split()))
res = 0
for k, i in enumerate(p_list):
  left_list = p_list[:k]
  if i == 1:
    res += 1
  else:
    filter_left = list(filter(lambda x: i > x, left_list))
    if len(filter_left) == 0:
      res += 1
print(res)

### FIXED CODE ###

n = int(input())
p_arr = list(map(int, input().split()))
min_i = 9999999999999999999999999
res = 0
for i in p_arr:
  if i == 1:
    res += 1
    break
  else:
    if i < min_i:
      res += 1
      min_i = i
print(res)
### BUGGY CODE ###

N,K,Q = map(int,input().split())
A = [int(input()) for _ in range(Q)]
Point_0 = [K for _ in range(N)]
for a in A:
    for i in range(N):
        if i != a-1:
            Point_0[i] -= 1
for p in Point_0:
    if p > 0:
        print("Yes")
    else:
        print("No")

### FIXED CODE ###

N,K,Q = map(int,input().split())
A = [int(input()) for _ in range(Q)]

Point_0 = [K-Q for _ in range(N)]
#(Point_0)
Point_Q = [0 for _ in range(N)]
for a in A:
    Point_Q[a-1] += 1
Point = [i+j for i,j in zip(Point_0,Point_Q)]
hantei = [print("Yes") if p>0 else print("No") for p in Point]
### BUGGY CODE ###

import sys
import math
from functools import reduce

# 入力を整数に変換して受け取る
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def MI1(): return map(int1, sys.stdin.readline().split())
# 入力全てを整数に変換したものの配列を受け取る
def LI(): return list(map(int, sys.stdin.readline().split()))
# 入力全てを整数に変換して1引いたものの配列を受け取る
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SR(): return sys.stdin.readline().rstrip()

ascii_lowercase = 'abcdefghijklmnopqrstuvwxyz'
ascii_uppercase = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
ascii_uppercase2 = 'ABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYZ'

# リストを改行区切りで出力する
p2D = lambda x: print(*x, sep="\n")
p2E = lambda x: print(''.join(x))
p2S = lambda x: print(*x, sep=" ")

def gcd_list(numbers):
    return reduce(math.gcd, numbers)

N = II()
S = input()

ans = 0
for i in range(1, N-2):
    for j in range(2, N):
        if j <= i:
            continue
        for k in range(3, N+1):
            if k <= j:
                continue
            if not(j-i == k-j or S[i-1] == S[j-1] or S[i-1] == S[k-1] or S[k-1] == S[j-1]):
                ans+=1
print(ans)

### FIXED CODE ###

import sys
import math
from functools import reduce

# 入力を整数に変換して受け取る
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def MI1(): return map(int1, sys.stdin.readline().split())
# 入力全てを整数に変換したものの配列を受け取る
def LI(): return list(map(int, sys.stdin.readline().split()))
# 入力全てを整数に変換して1引いたものの配列を受け取る
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SR(): return sys.stdin.readline().rstrip()

ascii_lowercase = 'abcdefghijklmnopqrstuvwxyz'
ascii_uppercase = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
ascii_uppercase2 = 'ABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYZ'

# リストを改行区切りで出力する
p2D = lambda x: print(*x, sep="\n")
p2E = lambda x: print(''.join(x))
p2S = lambda x: print(*x, sep=" ")

def gcd_list(numbers):
    return reduce(math.gcd, numbers)

N = int(input())
S = input()
ans = S.count("R") * S.count("G") * S.count("B")
for i in range(N-2):
  for j in range(i+1,N-1):
    k=2*j-i
    if k>=N:
      continue
    if S[i]!=S[j] and S[j]!=S[k] and S[k]!=S[i]:
      ans-=1
print(ans)
### BUGGY CODE ###

N, M = map(int, input().split())
L = [0] * M
R = [0] * M
ID = [0] * N
N = {i for i in range(1, N + 1)}
for i in range(M):
    L[i], R[i] = map(int, input().split())
    N = N.intersection({j for j in range(L[i], R[i] + 1)})

print(len(N))

### FIXED CODE ###

N, M = map(int, input().split())
L = [0] * M
R = [0] * M

for i in range(M):
    L[i], R[i] = map(int, input().split())
LL = max(L)
RR = min(R)
ans = 0
for i in range(N):
    if LL <= i + 1 <= RR:
        ans += 1
    else:
        pass
print(ans)
### BUGGY CODE ###

from collections import deque
s = deque(input())
num = int(input())
for i in range(num):
  a = deque(input().split())
  start = int(a[0])
  if start == 2:
    ns = int(a[1])
    if ns == 1:
      s.appendleft(a[2])
      #s = a[2] + s
    else:
      #s = s + a[2]
      s.append(a[2])
  else:
    s.reverse()
for i in range(len(s)):
  print(s[i], end='')

### FIXED CODE ###

from collections import deque
s = deque(input())
num = int(input())
cnt = 0
for i in range(num):
  a = input().split()

  if a[0] == '2':
    if (int(a[1])+cnt)%2==1:
      s.appendleft(a[2])
    else:
      s.append(a[2])
  else:
    cnt += 1
if cnt%2 == 1:    
	s.reverse()
print("".join(s))
### BUGGY CODE ###

import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")

M =998244353

n, s = map(int, input().split())
a = list(map(int, input().split()))
dp = [[0]* (s+1) for _ in range(n+1)]
for i in range(n+1):
    dp[i][0] = 2**i
for i in range(1,n+1):
    for j in range(1,s+1):
        dp[i][j] = dp[i-1][j]*2
        if j>=a[i-1]:
             dp[i][j] += dp[i-1][j-a[i-1]]
        dp[i][j] %= M
print(dp[n][s])

### FIXED CODE ###

import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")

M =998244353

n, s = map(int, input().split())
a = list(map(int, input().split()))
dp = [[0]* (s+1) for _ in range(n+1)]
for i in range(n+1):
    dp[i][0] = pow(2,i,M)
for i in range(1,n+1):
    for j in range(1,s+1):
        dp[i][j] = dp[i-1][j]*2
        if j>=a[i-1]:
             dp[i][j] += dp[i-1][j-a[i-1]]
        dp[i][j] %= M
print(dp[n][s])
### BUGGY CODE ###

import sys

def findLCS(X, Y):
    subx = list(set(X))
    suby = list(set(Y))
    extractSubsequence(X, subx[:], subx)
    extractSubsequence(Y, suby[:], suby)

    sublen = 0
    for sx in subx:
        for sy in suby:
            if sx == sy:
                sublen = len(sx)
    return sublen

def extractSubsequence(A, C, S):
    alen = len(A)
    flag = True
    while flag:
        for s in S:
            for c in C:
                sub = s + c
                if len(sub) > alen:
                    flag = False
                elif judgeSubInList(A, sub):
                    S.append(sub)

def judgeSubInList(A, sub):
    idx = 0
    slen = len(sub)
    for a in A:
        if a == sub[idx]:
            idx += 1
            if idx == slen:
                return True
    return False

lines = sys.stdin.readlines()
N = int(lines[0])

for i in range(N):
    X = lines[2 * i + 1].strip()
    Y = lines[2 * i + 2].strip()
    print findLCS(X, Y)

### FIXED CODE ###

import sys

def findLCS(X, Y):
    m, n = len(X), len(Y)
    C = [0] * (n + 1)

    for i in range(m):
        prev = C[:]
        for j in range(n):
            if X[i] == Y[j]:
                C[j + 1] = prev[j] + 1
            elif C[j + 1] < C[j]:
                C[j + 1] = C[j]

    return C[-1]

lines = sys.stdin.readlines()
N = int(lines[0])

for i in range(N):
    X = lines[2 * i + 1].strip()
    Y = lines[2 * i + 2].strip()
    print findLCS(X, Y)
### BUGGY CODE ###

import numpy as np
def so(n):
    if n < 2:
        return False
    elif n ==2:
        return True
    elif n % 2 == 0:
        return False
    for i in range(3, int(np.sqrt(n)) + 1, 2):
        if n % i == 0:
            return False
    return True
A, B = map(int, input().split())
M = np.min([A, B])
n = 0
for i in range(1, M + 1):
    if so(i):
        if (A % i == 0) and (B % i == 0):
            n = n + 1
print(n + 1)


### FIXED CODE ###

import numpy as np
def p(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a
A, B = map(int, input().split())
M = np.min([A, B])
a = p(A)
b = p(B)
t = set(a) & set(b)
print(len(t) + 1)
### BUGGY CODE ###

S = input()
Q = int(input())

for _ in range(Q):
    query = input()
    if query[0] == "1":
        S = S[::-1]
    else:
        T,F,C = query.split()
        if F=="1":
            S = C + S
        else:
            S = S + C
print(S)


### FIXED CODE ###

class Node:
    def __init__(self, v):
        self.v = v
        self.p = None
        self.n = None

class LinkedList:
    def __init__(self, v):
        self.head = Node(v)
        self.tail = self.head
        self.d = 1

    def reverse(self):
        self.d = self.d * -1

    def insertTail(self, v):
        node = Node(v)
        if self.d == 1:
            self.tail.n = node
            node.p = self.tail
            self.tail = node
        else:
            self.head.p = node
            node.n = self.head
            self.head = node

    def insertHead(self, v):
        self.reverse()
        self.insertTail(v)
        self.reverse()

    def toString(self):
        res = ""
        if self.d == 1:
            pos = self.head
            while pos != None:
                res = res + pos.v
                pos = pos.n
        else:
            pos = self.tail
            while pos != None:
                res = res + pos.v
                pos = pos.p
        return res

S = input()
Q = int(input())

l = LinkedList(S[0])
for i in range(1,len(S)):
    l.insertTail(S[i])

for _ in range(Q):
    query = input()
    if query[0] == "1":
        l.reverse()
    else:
        T,F,C = query.split()
        if F=="1":
            l.insertHead(C)
        else:
            l.insertTail(C)
print(l.toString())
### BUGGY CODE ###

K, S = map(int, input().split())
cnt = 0
for x in range(K+1):
    for y in range(S-x+1):
        if y <= K:
            z = S - x - y
            if z >= 0 and z <= K:
                cnt += 1
print(cnt)

### FIXED CODE ###

K, S = map(int, input().split())
cnt = 0
for x in range(K+1):
    for y in range(min(K,S-x)+1):
        z = S - x - y
        if z <= K:
            cnt += 1
print(cnt)