Harryxun/stf_run huggingface dataset:
suit = {"S": 0, "H": 1, "C": 2, "D": 3}
suit_keys = list(suit.keys())
deck = [[suit_keys[i] + " " + str(j + 1) for j in range(13)] for i in range(4)]

for _ in range(int(input())):
    card = input().split()
    deck[suit[card[0]]][int(card[1])] = ""

for i in range(4):
    for j in deck[i]:
        if j != "":
            print(j)


### FIXED CODE ###

suit = {"S": 0, "H": 1, "C": 2, "D": 3}
suit_keys = list(suit.keys())
deck = [[suit_keys[i] + " " + str(j + 1) for j in range(13)] for i in range(4)]
for _ in range(int(input())):
    card = input().split()
    deck[suit[card[0]]][int(card[1]) - 1] = ""
for i in range(4):
    for j in range(13):
        if deck[i][j] != "":
            print(deck[i][j])
import fractions
from functools import reduce


def gcd(*numbers):
    return reduce(fractions.gcd, numbers)


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


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


def aho(x):
  return x - X


B = list(map(aho, A))

C = gcd_list(B)

print(C)

### FIXED CODE ###

A, B = (int(i) for i in input().split())
if A % 2 == 0 or B % 2 == 0:
    print('No')
else:
    print('Yes')
from collections import Counter

pas = 0

H, W, M = map(int, input().split())
hn = []
wn = []
tli = []
for _ in range(M):
    h, w = map(int, input().split())
    tli.append([h,w])
    hn.append(h)
    wn.append(w)

hcnt = Counter(hn)
wcnt = Counter(wn)

ha, cha = zip(*hcnt.most_common())
wa, cwa = zip(*wcnt.most_common())

hli = [int(ha[0])]
wli = [int(wa[0])]
for i in range(len(cha)-1):
    if cha[i] == cha[i+1]:
        hli.append(int(ha[i+1]))
    else:
        break
for i in range(len(cwa)-1):
    if cwa[i] == cwa[i+1]:
        wli.append(int(wa[i+1]))
    else:
        break

for i in range(len(hli)):
    if pas == 1:
        break
    for k in range(len(wli)):
        if [hli[i], wli[k]] not in tli:
            ans = cha[i] + cwa[k]
            pas = 1
            break

if pas == 0:
    print(cha[0] + cwa[0] - 1)
else:
    print(ans)



### FIXED CODE ###

N, X, T = map(int, input().split())
 
ans = N//X

if N%X != 0:
    ans+=1
 
print(ans*T)
from heapq import *
import sys
from collections import *
from itertools import *
from decimal import *
import copy
from bisect import *
import math
sys.setrecursionlimit(4100000)
def gcd(a,b):
    if(a%b==0):return(b)
    return (gcd(b,a%b))
input=lambda :sys.stdin.readline().rstrip()


N=int(input())
X=input()
C=X.count("1")

lst=[]
lstcount=[]
for x in [C-1,C+1]:
    flg=0
    if C<=0:
        lst.append(0)
        lstcount.append(0)
    else:
        Z=0
        p=1
        for i in range(N):
            if X[-i-1]=="1":
                Z+=p
            p*=2
            if Z>=x:
                Z%=x
                flg=1
            if flg:
                p%=x
        lst.append(Z)
        lstcount.append(flg)
exit()
#print(lst)
fac1=[1]
fac2=[1]
C1=C-1
C2=C+1
for i in range(N):
    fac1.append(fac1[-1]*2%C1)
    fac2.append(fac2[-1]*2%C2)

for i in range(N):

    _C=C+(1 if X[i]=="0"  else -1 )
    if _C==0:
        print(0)
        continue
    if  X[i]=="0":
        lstidx=1
    else:
        lstidx=0

    idx=(N-1-i)

    value=lst[lstidx]+(fac2[idx] if  X[i]=="0" else fac1[idx])
    #print(lst[lstidx],value,_C)
    count=lstcount[lstidx]-1
    while value:
        count+=1
        value%=_C
        _C=0
        bit=value
        while bit:
            _C+=bit&1
            bit>>=1
    print(max(count,1))


### FIXED CODE ###

from heapq import *
import sys
from collections import *
from itertools import *
from decimal import *
import copy
from bisect import *
import math
sys.setrecursionlimit(4100000)
def gcd(a,b):
    if(a%b==0):return(b)
    return (gcd(b,a%b))
input=lambda :sys.stdin.readline().rstrip()


N=int(input())
X=input()
C=X.count("1")

lst=[]
lstcount=[]
for x in [C-1,C+1]:
    flg=0
    if x<=0:
        lst.append(0)
        lstcount.append(0)
    else:
        Z=0
        p=1
        for i in range(N):
            if X[-i-1]=="1":
                Z+=p
            p*=2
            if Z>=x:
                Z%=x
                flg=1
            if flg:
                p%=x
        lst.append(Z)
        lstcount.append(flg)
#print(lst)
fac1=[1]
fac2=[1]
C1=max(C-1,1)
C2=max(C+1,1)
for i in range(N):
    fac1.append(fac1[-1]*2%C1)
    fac2.append(fac2[-1]*2%C2)

for i in range(N):

    _C=C+(1 if X[i]=="0"  else -1 )
    if _C==0:
        print(0)
        continue
    if  X[i]=="0":
        lstidx=1
    else:
        lstidx=0

    idx=(N-1-i)

    value=lst[lstidx]+(fac2[idx] if  X[i]=="0" else -fac1[idx])
    #print(value,X[i]=="0",lst,C-1,C+1)
    bit=value
    count=0
    while value and _C:
        count+=1
        value%=_C
        _C=0
        bit=value
        while bit:
            _C+=bit&1
            bit>>=1
    print(max(count,1))
import sys


if __name__ == '__main__':
    # a not yum, bc yum
    a = int(sys.argv[1])
    b = int(sys.argv[2])
    c = int(sys.argv[3])

    if (a+b) >= c:
        print(b+c)
    else:
        print(a+b+1+b)


### FIXED CODE ###

import sys


if __name__ == '__main__':
    # a not yum, bc yum
    a, b, c = [int(i) for i in input().split()]

    if (a+b) >= c:
        print(b+c)
    else:
        print(a+b+1+b)
a = int(input())
if a%9==0:
  print('Yes')
else:
  print('No')
  


### FIXED CODE ###

import numpy as np
a,b,c = map(int,input().split())
print(int(np.ceil(a/b)*c))
N, M = map(int, input().split())
A = list(map(int, input().split()))
A.sort(reverse=True)

table = {1: 2, 2: 5, 3: 5, 4: 4, 5: 5, 6: 6, 7: 3, 8: 7, 9: 6}
a = [table[i] for i in A]

# ちょうどi本のマッチ棒を使って、条件を満たす整数を作るときの最大桁数
INF = 10 ** 9
dp = [-INF] * (N + 1)
dp[0] = 0
cost = set(a)

for i in range(1, N + 1):
    for j in cost:
        if i - j >= 0 and dp[i] < dp[i - j] + 1:
            dp[i] = dp[i - j] + 1

answer = []
for i in A:
    x = table[i]
    while N:
        if dp[N] == dp[N - x] + 1:
            answer.append(i)
            N -= x
        else:
            break

print(''.join(map(str, answer)))

### FIXED CODE ###

N, M = map(int, input().split())
A = list(map(int, input().split()))
A.sort(reverse=True)

table = {1: 2, 2: 5, 3: 5, 4: 4, 5: 5, 6: 6, 7: 3, 8: 7, 9: 6}
a = [table[i] for i in A]

# ちょうどi本のマッチ棒を使って、条件を満たす整数を作るときの最大桁数
INF = float('inf')
dp = [-INF] * (N + 1)
dp[0] = 0
cost = set(a)

for i in range(1, N + 1):
    for j in cost:
        if i - j >= 0 and dp[i] < dp[i - j] + 1:
            dp[i] = dp[i - j] + 1

answer = []
for i in A:
    x = table[i]
    while N - x >= 0 and dp[N] == dp[N - x] + 1:
        answer.append(i)
        N -= x

print(''.join(map(str, answer)))
s=input()
print("Bad" if s[0]==s[1] or s[1]==s[2] or s[2]==s[3] else "Good")

### FIXED CODE ###

n,l=map(int,input().split())
ans=0
chk=10000
for i in range(n):
    ans+=i+l
    if abs(chk)>abs(i+l):
        chk=i+l
print(ans-chk)
from collections import deque
n,m=map(int,input().split())
adj=[[] for _ in range(n)]
for _ in range(m):
  a,b =map(int,input().split())
  a-=1
  b-=1
  adj[a].append(b)
  adj[b].append(a)
ans=[0]*n
que=deque([])
que.append(0)
while que:
  e=que.popleft
  for i in adj[e]:
    if ans[i]!=0:
      continue
    ans[i]=e+1
    que.append(i)
print("Yes")
for i in range(1,n):
  print(ans[i])


### FIXED CODE ###

from collections import deque
n,m=map(int,input().split())
adj=[[] for _ in range(n)]
for _ in range(m):
  a,b =map(int,input().split())
  a-=1
  b-=1
  adj[a].append(b)
  adj[b].append(a)
ans=[0]*n
que=deque([])
que.append(0)
while que:
  e=que.popleft()
  for i in adj[e]:
    if ans[i]!=0:
      continue
    ans[i]=e+1
    que.append(i)
print("Yes")
for i in range(1,n):
  print(ans[i])
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N, M, S = mapint()
graph = [{} for _ in range(N)]
for _ in range(M):
    u, v, a, t = mapint()
    graph[u-1][v-1] = (a, t)
    graph[v-1][u-1] = (a, t)

change = [list(mapint()) for _ in range(N)]
from heapq import heappop, heappush
# time, silver, vertex
Q = [(0, S, 0)]
dist = [[10**18]*2501 for _ in range(N)]
dist[0][S] = 0

while Q:
    t, s, v = heappop(Q)
    rate, change_time = change[v]
    if s<2500 and dist[v][min(2500, s+rate)]>t+change_time:
        dist[v][min(2500, s+rate)] = t+change_time
        heappush(Q, (t+change_time, min(2500, s+rate), v))
    for nx in graph[v].keys():
        nx_s, nx_t = graph[v][nx]
        if nx_s<=s and dist[nx][s-nx_s]>t+nx_t:
            dist[nx][s-nx_s] = t+nx_t
            heappush(Q, (t+nx_t, s-nx_s, nx))
for i in range(1, N):
    print(min(dist[i]))

### FIXED CODE ###

import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N, M, S = mapint()
S = min(S, N*50)
query = [[[] for _ in range(N*50+1)] for _ in range(N)]
for _ in range(M):
    u, v, a, b = mapint()
    for coin in range(a, N*50+1):
        query[u-1][coin].append((v-1, a, b))
        query[v-1][coin].append((u-1, a, b))
for i in range(N):
    c, d = mapint()
    for coin in range(N*50+1):
        query[i][coin].append((i, -c, d))

inf = 10**18
dp = [[inf]*(N*50+1) for _ in range(N)]
dp[0][0] = 0

import heapq
queue = [(0, 0, S)]
checked = [0]*N
cnt = 0

while queue:
    t, now, coin = heapq.heappop(queue)
    if cnt==N:
        break
    if not checked[now]:
        checked[now] = 1
        cnt += 1
    qlis = query[now][coin]
    for nx, a, b in qlis:
        if 0<=coin-a:
            coin = min(coin, N*50+a)
            if t+b<dp[nx][coin-a]:
                dp[nx][coin-a] = t+b
                heapq.heappush(queue, (t+b, nx, coin-a))

for i in range(1, N):
    print(min(dp[i]))
import math

r = 100000000
sqrt = math.sqrt(r)
p = [1 for i in range(r)]
p[0] = 0
for i in range(1,sqrt):
    if p[i]:
        p[2*i+1::i+1] = [0 for x in range(2*i+1,r,i+1)]

count = 0
while True:
    try:
        n = int(raw_input())
        if p[n-1]:
            count += 1
    except:
        break
print count

### FIXED CODE ###

def isPrime(p):
	if p == 2: return 1
	if p < 2 or p&1 == 0: return 0
	return 1 if pow(2,p-1,p) == 1 else 0
	
n = int(raw_input())
print sum(isPrime(int(raw_input())) for i in range(n))
s1,s2,s3 = list(map(str,input(),split()))
s1,s2,s3 = map(str.upper())
print( s1[0] + s2[0] + s3[0])

### FIXED CODE ###

s1,s2,s3=map(str,input().upper().split()) #文字列
print(s1[0]+s2[0]+s3[0])
N = int(input())
count = 0
end = 0
start = 0
double = 0
for i in range(N):
    line = input()
    if "AB" in line:
        count += 1
    if line[0] == "B":
        if line[-1] == "A":
            double +=1
        else:
            start += 1
    if line[-1] == "A":
        if line[0] == "B":
            double +=1
        else:
            end += 1
if double == 0:
    count += min(start, end)
elif start + end > 0:
    counr += double + min(start, end)
elif start + end == 0:
    count += double - 1
print(count)
        

### FIXED CODE ###

N = int(input())
count = 0
end = 0
start = 0
double = 0
for i in range(N):
    line = input()
    if "AB" in line:
        count += line.count("AB")
    if line[0] == "B":
        if line[-1] == "A":
            double +=1
        else:
            start += 1
    elif line[-1] == "A":
            end += 1
if double == 0:
    count += min(start, end)
elif start + end > 0:
    count += double + min(start, end)
elif start + end == 0:
    count += double - 1
print(count)
import math
import copy

inputa = input().split()
# inputb = input().split()
# inputc = input().split()

a = int(inputa[0])
b = int(inputa[1])
c = int(inputa[2])

# inputb = input().split()
# inputbint = [int(x) for x in inputb]
# inputList = list(b)

# x = int(inputb[0])
# y = int(inputb[1])

# inputList=[]
# for i in range(a):
#     inputNum = input().split()
#     inputNum = [int(x) for x in inputNum]
#     inputList.append(inputNum)

# inputList = [int(n) for n in inputList]

# b = [int(n) for n in inputb]
# c = [int(n) for n in inputc]

min = min[a, b]
cnt = 0

for i in range(min, 0, -1):
    checka = a % i
    checkb = b % i
    if checka == 0 and checkb == 0:
        cnt += 1
        if cnt == k:
            print(i)
            

### FIXED CODE ###

import math
import copy

inputa = input().split()
# inputb = input().split()
# inputc = input().split()

a = int(inputa[0])
b = int(inputa[1])
c = int(inputa[2])

# inputb = input().split()
# inputbint = [int(x) for x in inputb]
# inputList = list(b)

# x = int(inputb[0])
# y = int(inputb[1])

# inputList=[]
# for i in range(a):
#     inputNum = input().split()
#     inputNum = [int(x) for x in inputNum]
#     inputList.append(inputNum)

# inputList = [int(n) for n in inputList]

# b = [int(n) for n in inputb]
# c = [int(n) for n in inputc]

min = min([a, b])
cnt = 0

for i in range(min, 0, -1):
    checka = a % i
    checkb = b % i
    if checka == 0 and checkb == 0:
        cnt += 1
        if cnt == c:
            print(i)
n=int(input());a=[int(input())for i in range(n)];m=int(input());b=[int(input())for i in range(m)];ans=0
for i in a:ans=max(a.count(i)-b.count(i),ans)
print(ans)

### FIXED CODE ###

n=int(input());a=[input()for i in range(n)];m=int(input());b=[input()for i in range(m)];ans=0
for i in a:ans=max(a.count(i)-b.count(i),ans)
print(ans)
８N = int(input())
A = []#生徒たちが出席した順番
rev = [0]*N #早く来た順の生徒の番号

for x in input().split():
    A.append(int(x))

for i in range(N):
    rev[A[i]-1] = i+1

print(' '.join(map(str,rev)))

### FIXED CODE ###

N = int(input())
A = []#生徒たちが出席した順番
rev = [0]*N #早く来た順の生徒の番号

for x in input().split():
    A.append(int(x))

for i in range(N):
    rev[A[i]-1] = i+1

print(' '.join(map(str,rev)))
import math
a,b =input().split()
a = int(a)
b = float((int(int(b)*100))/100)
c = math.floor(a*b)
print(c)

### FIXED CODE ###

a,b = input().split()
a = int(a)
b = int(b.replace('.',''))
print(a*b//100)
h,w=map(int,input().split())
s=[int for _ in range (h)]
for i in range(h):
  l=""
  for j in range(w):
    if s[i][j]=="#":
      l+="#"
    else:
      l+=str(sum([t[max(0,j-1):min(w,j+2)].count("#") for t in s[max(0,i-1):min(h,i+2)]]))
print(l)

### FIXED CODE ###

h,w=map(int,input().split())
s=[input() for _ in range(h)]
for i in range(h):
    l=""
    for j in range(w):
        if s[i][j]=="#":
            l+="#"
        else:
            l+=str(sum([t[max(0,j-1):min(w,j+2)].count("#") for t in s[max(0,i-1):min(h,i+2)]]))
    print(l)
s1,s2,s3 = map(str,input())
bs1 = s1.upper()
bs2 = s2.upper()
bs3 = s3.upper()
print(bs1[0]+bs2[0]+bs3[0])

### FIXED CODE ###

s1,s2,s3 = map(str,input().split())
bs1 = s1.upper()
bs2 = s2.upper()
bs3 = s3.upper()
print(bs1[0]+bs2[0]+bs3[0])
n = int(input())
a = list(map(int, input().split()))
pro = 0
b = a[0]
for i in range(n):
    if a[i]>b:
        pro = 1
        break
if pro==0:
    print('1000')
else:
    sum = 1000
    t = 0
    if n>3 :
        while sum > 0 and t< n-3:
            if a[t]>a[t+1]:
                continue
            else:
                if a[t+1]>a[t+2]:
                    num = sum // a[t]
                    sum = sum + a[t+1]*num - a[t]*num
                    t=t+1
                
                else :
                    num = sum // a[t]
                    sum = sum + a[t+2]*num - a[t]*num
                    a.pop(t+2)
            t = t+1
    elif n == 3:
        if a[1]>a[2]:
            num = sum // a[0]
            sum = sum + a[1]*num - a[0]*num
                
        else :
            num = sum // a[0]
            sum = sum + a[2]*num - a[0]*num
    else:
        num = sum // a[0]
        sum = sum + a[1]*num - a[0]*num
    print(sum)

### FIXED CODE ###

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

Stock = 0
Money = 1000
 
for i in range(N-1):
    if A[i] < A[i + 1]:

        Stock = Money // A[i]
        Money %= A[i]
        Money += Stock * A[i+1]
print(Money)
h,w = map(int, input().split())
for i in h:
  a[i] = list(input())

a = {}
b = []

for i in h+2:
  b.append('#')

a.insert(0,b)
a.insert(h+2,b)

for i in w+2:
  a[i].insert(0,'#')
  a[i].insert(w+2,'#')

print(a)

### FIXED CODE ###

h,w = map(int, input().split())
a = [input().split() for i in range(h)]
b = []
 
for i in range(h):
  a[i].insert(0,'#')
  a[i].append('#')
  
for i in range(w+2):
  b.append('#')
 
a.insert(0,b)
a.append(b)
  
for i in a:
  print("".join(list(map(str,i))))
s = input()
k = int(input())
if s[0] == "1":
  if s[:k] == "1"*k:
    print(s[0])
  else:
    print(s[k-1])
else:
  print(s[0])

### FIXED CODE ###

s = input()
k = int(input())
front1 = 0
if s == "1":
  print(1)
  exit()
for i in range(len(s)):
  if s[i] == "1":
    front1 += 1
  else:
    break
print(s[min(k-1, front1)])
N = int(input())
edges = []
connected = [[] for i in range(N+1)]
for i in range(N-1):
    x=list(map(int, input().split()))
    x[0] -= 1
    x[1] -= 1
    edges.append(x)
    connected[x[0]].append([x[1], x[2]])
    connected[x[1]].append([x[0], x[2]])

Q,K = map(int, input().split())
K -= 1
depth = [0]*N
def DFS(v, p, d):
    depth[v] = d
    for child in connected[v]:
        if child[0] == p:
            continue
        DFS(child[0], v, d+child[1])

DFS(K,-1,0)
for i in range(Q):
    xi, yi = map(int, input().split())
    print(depth[xi-1]+depth[yi-1])

    


### FIXED CODE ###

import sys
sys.setrecursionlimit(200000)

N = int(input())
edges = []
connected = [[] for i in range(100010)]
for i in range(N-1):
    x=list(map(int, input().split()))
    x[0] -= 1
    x[1] -= 1
    edges.append(x)
    connected[x[0]].append([x[1], x[2]])
    connected[x[1]].append([x[0], x[2]])

Q,K = map(int, input().split())
K -= 1
depth = [0]*100010
def DFS(v, p, d):
    depth[v] = d
    for child in connected[v]:
        if child[0] == p:
            continue
        DFS(child[0], v, d+child[1])

DFS(K,-1,0)
for i in range(Q):
    xi, yi = map(int, input().split())
    print(depth[xi-1]+depth[yi-1])
import numpy as np
import heapq
initial = 10 ** 15

def di(link_costs, s):
    costs = [initial] * n
    costs[s] = 0
    node_list = []
    serched_node = set()
    heapq.heappush(node_list, (0, s))
    
    while(len(node_list) != 0 and len(serched_node) != n):
        index = heapq.heappop(node_list)[1]
        if index in serched_node:
            continue
        serched_node.add(index)
        link = links[index]
        for j in link:
            if j in serched_node:
                continue
        
            cost = link_costs[index][j]
            newcost =  costs[index] + cost
            if newcost < costs[j]:
                costs[j] = newcost
                heapq.heappush(node_list, (newcost, j))
    return costs
    
n, m, s, t  = list(map(int, input().split()))
s -= 1
t -= 1
links = [set() for _ in range(n)]
links_cost_en = np.full((n, n), initial)
links_cost_sn = np.full((n, n), initial)

for _ in range(m):
    u, v, a, b  = list(map(int, input().split()))
    links[u-1].add(v-1)
    links[v-1].add(u-1)
    links_cost_en[u - 1][v - 1] = a
    links_cost_en[v - 1][u - 1] = a
    links_cost_sn[u - 1][v - 1] = b
    links_cost_sn[v - 1][u - 1] = b

cost_en_from_s = di(links_cost_en, s)
cost_sn_to_t = di(links_cost_sn, t)
cost_list = [cost_en_from_s[i] + cost_sn_to_t[i] for i in range(n)]
 
ans = [initial] * n
ans[-1] = cost_list[-1]
for i in list(range(n - 1))[::-1]:
    ans[i] = min(ans[i + 1], cost_list[i])
for i in range(n):
    print(initial - int(ans[i]))

### FIXED CODE ###

import heapq
initial_cost = 10 ** 9
initial = 10 ** 15

def di(link_costs, s):
    costs = [initial] * n
    costs[s] = 0
    q = []
    heapq.heappush(q, (0, s))
    
    while(len(q) != 0):
        index_cost, index = heapq.heappop(q)
        if costs[index] < index_cost:
            continue

        for j in link_costs[index]:
            newcost = costs[index] + link_costs[index][j]
            if newcost < costs[j]:
                costs[j] = newcost
                heapq.heappush(q, (newcost, j))
    return costs
    
n, m, s, t  = list(map(int, input().split()))
s -= 1
t -= 1
links_cost_en = [{} for _ in range(n)]
links_cost_sn = [{} for _ in range(n)]

for _ in range(m):
    u, v, a, b  = list(map(int, input().split()))
    u -= 1
    v -= 1
    links_cost_en[u][v] = a
    links_cost_en[v][u] = a
    links_cost_sn[u][v] = b
    links_cost_sn[v][u] = b

cost_en_from_s = di(links_cost_en, s)
cost_sn_to_t = di(links_cost_sn, t)
cost_list = [cost_en_from_s[i] + cost_sn_to_t[i] for i in range(n)]

ans = [initial] * n
ans[-1] = cost_list[-1]
for i in list(range(n - 1))[::-1]:
    ans[i] = min(ans[i + 1], cost_list[i])
for i in range(n):
    print(initial - ans[i])
N = int(input())

talk = [[-1 for i in range(N)] for j in range(N)]

for i in range(N):
    A = int(input())
    for j in range(A):
        x, y = map(int, input().split())
        talk[i][x-1] = y

ans = 0

for i in range(1 << N):
    honest = []
    ansi = 0
    for j in range(N):
        if(1 << j and i):
            honest.append(1)
        else:
            honest.append(0)

    for j in range(N):
        if(honest[i] == 0):
            continue
        flag = True
        for k in range(N):
            if(honest[k] != talk[j][k] and talk[j][k] != -1):
                flag = False

        if(flag):
            ansi += 1

    ans = max(ans, ansi)

print(ans)



### FIXED CODE ###

N = int(input())
people = [[-1 for __ in range(N)] for _ in range(N)]
for i in range(N):
    A = int(input())
    for j in range(A):
        x, y = map(int, input().split())
        x -= 1
        people[i][x] = y

ans = 0


for i in range(1 << N):
    ansi = 0
    flag = True
    for j in range(N):
        peoplei = 0
        if (i & 1 << j):
            peoplei = 1
            ansi += 1
        for k in range(N):
            if (i & 1 << k):
                if(people[k][j] != -1 and people[k][j] != peoplei):
                    flag = False

    if flag:
        ans = max(ans, ansi)


print(ans)
n-int(input())
a=int(input())
k = n%500
if k<=a:print('Yes')
else:print('No')

### FIXED CODE ###

n=int(input())
a=int(input())
k = n%500
if k<=a:print('Yes')
else:print('No')
#!/usr/bin/env python
# -*- coding: utf-8 -*-


import sys
import math

def dig(n):
  return int(math.log10(n))

num = input()
count = 0
for i in range(num):
  num1 = []
  s = input()
  t = input()
  if dig(s) > 80 or dig(t) > 80 or dig(s+t) > 80 :
    print "overflow"
  else:
    print s+t

### FIXED CODE ###

#!/usr/bin/env python
# -*- coding: utf-8 -*-


import sys

num = input()
for i in range(num):
  s = long(input())
  t = long(input())
  u = s+t
  if len(str(u)) > 80 :
    print "overflow"
  else:
    print u
times, questions = [int(a) for a in input().split()]

strings = str(input())

for i in range(questions):
    for j in range(times):
        start, end = [int(a) for a in input().split()]
        moji = strings[start - 1: end]
        counts = 0
        for k in range(len(moji) - 1):
            if moji[k] == 'A' and moji[k + 1] == 'C':
                counts += 1
        print(counts)

### FIXED CODE ###

N, Q = map(int, input().split())
S = input()
t = [0] * (N + 1)
for i in range(N):
    t[i + 1] = t[i] + (1 if S[i : i + 2] == 'AC' else 0)
for i in range(Q):
    l, r = map(int, input().split())
    print(t[r-1] - t[l-1])
# -*- coding: utf-8 -*-
import functools


def lcs(x, y):
    n = len(x)
    m = len(y)
    return rec(x, y, n, m)


@functools.lru_cache(maxsize=None)
def rec(x, y, i, j):
    if i == 0 or j == 0:
        return 0
    elif x[i - 1] == y[j - 1]:
        return rec(x, y, i - 1, j - 1) + 1
    else:
        return max(rec(x, y, i, j - 1), rec(x, y, i - 1, j))


if __name__ == '__main__':
    import sys
    q = int(sys.stdin.readline().strip())
    for i in range(q):
        x = sys.stdin.readline().strip()
        y = sys.stdin.readline().strip()
        print(lcs(x, y))



### FIXED CODE ###

def m():
 e=input
 a=''
 for _ in[0]*int(e()):
  X,z=e(),[]
  for y in e():
   s=i=0
   for k in z:
    t=X.find(y,s)+1
    if t<1:break
    if t<k:z[i]=t
    s=k;i+=1
   else:
    t=X.find(y,s)+1
    if t:z+=[t]
  a+=f'\n{len(z)}'
 print(a[1:])
if'__main__'==__name__:m()