CodeEff/ECCO huggingface dataset:
# Original solution
import sys
input = sys.stdin.readline

def cumsum_2d(inlist,h,w):
    outlist = [ [ inlist[i-1][j-1] if i != 0 and j != 0 else 0 for i in range(k+1) ] for j in range(k+1) ]
    for i in range(1,h+1):
        tmp = 0
        for j in range(1,w+1):
            tmp += outlist[i][j]
            outlist[i][j] = tmp
    for i in range(1,w+1):
        tmp = 0
        for j in range(1,h+1):
            tmp += outlist[j][i]
            outlist[j][i] = tmp

    return outlist
    
n, k = [ int(v) for v in input().split() ]
hope = [ [ a for a in input().split() ] for i in range(n) ]

b_board = [ [ 0 for i in range(k)] for j in range(k) ]
w_board = [ [ 0 for i in range(k)] for j in range(k) ]



for h, w, c in hope:
    a1, a2 = divmod(int(w),k)
    b1, b2 = divmod(int(h),k)
    if (a1+b1) % 2 == 1:
        if c == "B":
            c = "W"
        else:
            c = "B"

    if c == "B":
        b_board[int(h)%k][int(w)%k] += 1
    else:
        w_board[int(h)%k][int(w)%k] += 1
    
b_board_3 = cumsum_2d(b_board,k,k)
w_board_3 = cumsum_2d(w_board,k,k)


total_b, total_w = b_board_3[k][k], w_board_3[k][k]
ans = 0

for i in range(1,k+1):
    for j in range(1,k+1):
        b1 = b_board_3[i][j] - b_board_3[0][j] - b_board_3[i][0]
        b2 = total_b - b_board_3[i][k] - b_board_3[k][j] + b_board_3[i][j]
        w1 = w_board_3[i][j] - w_board_3[0][j] - w_board_3[i][0]
        w2 = total_w - w_board_3[i][k] - w_board_3[k][j] + w_board_3[i][j]
        ans = max(b1+b2+(total_w-w1-w2),w1+w2+(total_b-b1-b2),ans)

print(ans)


# Optimized solution
import sys
input = sys.stdin.readline

def cumsum_2d(inlist,h,w):
    
    outlist = [ [ inlist[i-1][j-1] if i != 0 and j != 0 else 0 for i in range(k+1) ] for j in range(k+1) ]
    for i in range(1,h+1):
        tmp = 0
        for j in range(1,w+1):
            tmp += outlist[i][j]
            outlist[i][j] = tmp
    for i in range(1,w+1):
        tmp = 0
        for j in range(1,h+1):
            tmp += outlist[j][i]
            outlist[j][i] = tmp

    return outlist
    
n, k = [ int(v) for v in input().split() ]
hope = [ [ a for a in input().split() ] for i in range(n) ]

b_board = [ [ 0 for i in range(k)] for j in range(k) ]
w_board = [ [ 0 for i in range(k)] for j in range(k) ]



for h, w, c in hope:
    a1, a2 = divmod(int(w),k)
    b1, b2 = divmod(int(h),k)
    if (a1+b1) % 2 == 1:
        if c == "B":
            c = "W"
        else:
            c = "B"

    if c == "B":
        b_board[b2][a2] += 1
    else:
        w_board[b2][a2] += 1
    
b_board_3 = cumsum_2d(b_board,k,k)
w_board_3 = cumsum_2d(w_board,k,k)


total_b, total_w = b_board_3[k][k], w_board_3[k][k]
ans = 0

for i in range(1,k+1):
    for j in range(1,k+1):
        b1 = b_board_3[i][j] - b_board_3[0][j] - b_board_3[i][0]
        b2 = total_b - b_board_3[i][k] - b_board_3[k][j] + b_board_3[i][j]
        w1 = w_board_3[i][j] - w_board_3[0][j] - w_board_3[i][0]
        w2 = total_w - w_board_3[i][k] - w_board_3[k][j] + w_board_3[i][j]
        ans = max(b1+b2+(total_w-w1-w2),w1+w2+(total_b-b1-b2),ans)

print(ans)
# Original solution
n, k = list(map(int, input().split()))
favor = [tuple(input().split()) for _ in range(n)]
square = [[0 for _ in range(k)] for _ in range(k)]
initscore = 0
for xc, yc, c in favor:
    x = int(xc)
    y = int(yc)
    x %= 2*k
    y %= 2*k
    if (x in range(k) and y in range(k)) or (x in range(k, 2*k) and y in range(k, 2*k)):
        if c == 'B':
            square[x%k][y%k] += 1
        else:
            square[x%k][y%k] -= 1
            initscore += 1
    else:
        if c == 'B':
            square[x%k][y%k] -= 1
            initscore += 1
        else:
            square[x%k][y%k] += 1
cum = [[0 for _ in range(k+1)] for _ in range(k+1)]
for i in range(k):
    for j in range(k):
        cum[i+1][j+1] = cum[i+1][j] + cum[i][j+1] - cum[i][j] + square[i][j]
maxscore = 0
for i in range(k):
    for j in range(k):
        score1 = 2*cum[i][j] + cum[k][k] - cum[i][k] - cum[k][j]
        score2 = cum[k][k] - score1
        maxscore = max(maxscore, initscore + max(score1, score2))
print(maxscore)

# Optimized solution
n, k = list(map(int, input().split()))
favor = [tuple(input().split()) for _ in range(n)]
square = [[0 for _ in range(k)] for _ in range(k)]
initscore = 0
for xc, yc, c in favor:
    x = int(xc)
    y = int(yc)
    x %= 2*k
    y %= 2*k
    if (x in range(k) and y in range(k)) or (x in range(k, 2*k) and y in range(k, 2*k)):
        if c == 'B':
            square[x%k][y%k] += 1
        else:
            square[x%k][y%k] -= 1
            initscore += 1
    else:
        if c == 'B':
            square[x%k][y%k] -= 1
            initscore += 1
        else:
            square[x%k][y%k] += 1
cum = [[0 for _ in range(k+1)] for _ in range(k+1)]
for i in range(k):
    for j in range(k):
        cum[i+1][j+1] = cum[i+1][j] + cum[i][j+1] - cum[i][j] + square[i][j]
maxscore = 0
for i in range(k):
    for j in range(k):
        score = cum[i][k] + cum[k][j] - 2*cum[i][j]
        maxscore = max(maxscore, max(cum[k][k] - score, score))
print((maxscore + initscore))
# Original solution
import sys
from collections import defaultdict

if __name__ == '__main__':
    n, v = list(map(int, sys.stdin.readline().split()))
    a = list(map(int, sys.stdin.readline().split()))
    b = list(map(int, sys.stdin.readline().split()))
    c = list(map(int, sys.stdin.readline().split()))
    d = list(map(int, sys.stdin.readline().split()))
    mp = defaultdict(int)
    ls = []
    for val1 in c:
        for val2 in d:
            mp[val1+val2] += 1
    ans = 0
    for val1 in a:
        for val2 in b:
           ans += mp[v-val1-val2]
    print(ans)



# Optimized solution
import sys
from collections import defaultdict

if __name__ == '__main__':
    n, v = list(map(int, sys.stdin.readline().split()))
    a = tuple(map(int, sys.stdin.readline().split()))
    b = tuple(map(int, sys.stdin.readline().split()))
    c = tuple(map(int, sys.stdin.readline().split()))
    d = tuple(map(int, sys.stdin.readline().split()))
    mp = defaultdict(int)
    ls = []
    for val1 in c:
        for val2 in d:
            mp[val1+val2] += 1
    ans = 0
    for val1 in a:
        for val2 in b:
           ans += mp[v-val1-val2]
    print(ans)
# Original solution
# -*- coding: utf-8 -*-
"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_4_A
AC
"""
import sys
from sys import stdin
from bisect import bisect_right, bisect_left
input = stdin.readline


def main(args):
    N, V = list(map(int, input().split()))
    A = [int(x) for x in input().split()]
    B = [int(x) for x in input().split()]
    C = [int(x) for x in input().split()]
    D = [int(x) for x in input().split()]

    #AB = []
    #for i in A:
    #    for j in B:
    #       AB.append(i+j)
    AB = [a+b for a in A for b in B]
    #AB.sort()

    #CD = [float('-inf'), float('inf')]
    #for i in C:
    #    for j in D:
    #       CD.append(i+j)
    CD = [c+d for c in C for d in D]
    CD.append(float('-inf'))
    CD.append(float('inf'))
    CD.sort()

    count = 0
    for ab in AB:
        i = bisect_left(CD, V - ab)
        j = bisect_right(CD, V - ab)
        count += max((j-i), 0)

    print(count)


if __name__ == '__main__':
    main(sys.argv[1:])

# Optimized solution
# -*- coding: utf-8 -*-
"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_4_A
AC
"""
import sys
from sys import stdin
from bisect import bisect_right, bisect_left
input = stdin.readline


def main(args):
    N, V = list(map(int, input().split()))
    A = [int(x) for x in input().split()]
    B = [int(x) for x in input().split()]
    C = [int(x) for x in input().split()]
    D = [int(x) for x in input().split()]

    AB = tuple(a+b for a in A for b in B)

    CD = [c+d for c in C for d in D]
    CD.append(float('-inf'))
    CD.append(float('inf'))
    CD.sort()

    count = 0
    for ab in AB:
        i = bisect_left(CD, V - ab)
        j = bisect_right(CD, V - ab)
        count += (j-i)

    print(count)


if __name__ == '__main__':
    main(sys.argv[1:])
# Original solution
A = list(map(int, input().split()))
B = list(map(int, input().split()))
max_sum = max([sum(A), sum(B)])
print(max_sum)

# Optimized solution
A, B = [list(map(int, input().split())) for _ in range(2)]
print((max([sum(A), sum(B)])))
# Original solution
#!/usr/bin/env python
# -*- coding: utf-8 -*-

"""
input:
2 20
5 9
4 10

output:
9

1 ??? N ??? 100
1 ??? vi ??? 100
1 ??? wi ??? 10,000,000
1 ??? W ??? 1,000,000,000
"""

import sys
from collections import namedtuple

MAX_N, MAX_V = 100, 100


def solve():
    dp = [[float('inf')] * (MAX_N * MAX_V + 1) for _ in range(MAX_N + 1)]
    dp[0][0] = 0
    for i, item in enumerate(item_list):
        v, w = item.value, item.weight
        for j in range(MAX_N * MAX_V + 1):
            if j < v:
                dp[i + 1][j] = dp[i][j]
            else:
                dp[i + 1][j] = min(dp[i][j], dp[i][j - v] + w)

    ans = 0
    for i in range(MAX_N * MAX_V + 1):
        if dp[c_items][i] <= real_cp:
            ans = i

    return ans


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    c_items, real_cp = list(map(int, _input[0].split()))
    items = [x.split() for x in _input[1:]]

    Item = namedtuple('Item', ('value', 'weight'))
    item_list = [Item(int(v), int(w)) for v, w in items]

    print((solve()))

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

"""
input:
2 20
5 9
4 10

output:
9

1 ??? N ??? 100
1 ??? vi ??? 100
1 ??? wi ??? 10,000,000
1 ??? W ??? 1,000,000,000
"""

import sys
from collections import namedtuple

MAX_V = 100


def solve():
    dp = [[float('inf')] * (c_items * MAX_V + 1) for _ in range(c_items + 1)]
    dp[0][0] = 0
    for i, item in enumerate(item_list):
        v, w = item.value, item.weight
        for j in range(c_items * MAX_V + 1):
            if j < v:
                dp[i + 1][j] = dp[i][j]
            else:
                dp[i + 1][j] = min(dp[i][j], dp[i][j - v] + w)

    ans = 0
    for i in range(c_items * MAX_V + 1):
        if dp[c_items][i] <= knapsack_cp:
            ans = i

    return ans


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    c_items, knapsack_cp = list(map(int, _input[0].split()))
    items = [x.split() for x in _input[1:]]

    Item = namedtuple('Item', ('value', 'weight'))
    item_list = [Item(int(v), int(w)) for v, w in items]

    print((solve()))
# Original solution
n, k = list(map(int, input().split()))
d = [11, 16, 10, 25, 9, 24, 19, 13, 18, 12, 17]
print((len([x for x in range(d[k], 7 * (n - 1), 11) if x % 7 > 1])))


# Optimized solution
n, k = list(map(int, input().split()))
d = [11, 16, 10, 25, 9, 24, 19, 13, 18, 12, 17]
e = 7 * (n - 1)
r = (e - d[k] - 1) // 77
print((5 * r + len([x for x in range(d[k] + 77 * r, e, 11) if x % 7 > 1])))
# Original solution
n, k = list(map(int, input().split()))

c = 0
for i in range(2, n):
    for j in range(2, 7):
        if (7 * i + j - 7) * 9 % 11 == k:
            c += 1

print(c)

# Optimized solution
n, k = list(map(int, input().split()))

p = int((n - 2) / 11)
c = p * 5
for i in range(2 + p * 11 , n):
    for j in range(2, 7):
        if (7 * i + j - 7) * 9 % 11 == k:
            c += 1

print(c)
# Original solution
n,k=list(map(int,input().split()))
#(i,j)=7i+j-7
x=0
for i in range(11):
    if (9*i)%11==k:
        x=i
        break
ans=0
for i in range((7*n)//11+1):
    s=11*i+x
    if s>7*n-7:
        continue
    if s<=7:
        continue
    if s%7==0 or s%7==1:
        continue
    else:
        ans+=1
print(ans)


# Optimized solution
n,k=list(map(int,input().split()))
#(i,j)=7i+j-7
x=0
for i in range(11):
    if (9*i)%11==k:
        x=i
        break
K=0
L=0
for i in range(1,78):
    if i%11!=x:
        continue
    if i%7<=1:
        continue
    K+=1
    if i<=7:
        L+=1
P=0
for i in range(1,7*(n%11)+1):
    if i%11!=x:
        continue
    if i%7<=1:
        continue
    if i>(7*(n%11)-7):
        continue
    P+=1
print((K*(n//11)+P-L))
# Original solution
n,k = list(map(int,input().split()))

count = 0

for i in range(1,6):
	for j in range(1,n-1):
		if (9*i+9+63*j)%11 == k:
			count += 1
print(count)

# Optimized solution
n,k = list(map(int,input().split()))

a = 4;b = 2;c = 0;d = 9;e = 7
f = [a,b,c,d,e]
ans = 0
for i in range((n-2)%11):
	if k in (a,b,c,d,e):
		ans += 1
	a = (a+8)%11
	b = (b+8)%11
	c = (c+8)%11
	d = (d+8)%11
	e = (e+8)%11

print((ans+((n-2)//11)*5))
# Original solution
#! /usr/bin/env python3

n, k = list(map(int, input().split()))
M = [[(7*i+j-7)%11 for j in range(1, 7+1)] for i in range(1, n+1)]
cnt = 0
f = lambda i, j : sum(M[i+y][j+x] for y in range(3) for x in range(3)) % 11 == k
h = [0] * 11
for i in range(min(n-2, 11)):
    for j in range(7-2):
        if f(i, j) :
            h[i] += 1
cnt = sum(h) * (n // 11)
for i in range(n % 11 - 2):
    cnt += h[i%11]
print(cnt)

# Optimized solution
#! /usr/bin/env python3

n, k = list(map(int, input().split()))
M = [[7*i+j-7 for j in range(1, 7+1)] for i in range(1, min(n+1, 14))]
cnt = 0
f = lambda i, j : sum(M[i+y][j+x] for y in range(3) for x in range(3)) % 11 == k
h = [0] * 11
for i in range(min(max(0, n-2), 11)):
    for j in range(7-2):
        if f(i, j) :
            h[i] += 1
cnt = sum(h) * ((n-2) // 11)
for i in range((n-2) % 11):
    cnt += h[i]
print(cnt)
# Original solution
#! /usr/bin/env python3

n, k = list(map(int, input().split()))
n = max(0, n-2)
ans = 0
f = lambda i, j : sum(7*(i+x//3+1)+(j+x%3+1)-7 for x in range(9)) % 11 == k
h = [0] * 11
for i in range(min(n, 11)):
    h[i] = sum(1 for x in range(5) if f(i, x))
ans = sum(h) * (n // 11) + sum(h[i] for i in range(n % 11))
print(ans)

# Optimized solution
#! /usr/bin/env python3

n, k = list(map(int, input().split()))
n = max(0, n-2)
ans = 0
h = [sum((63*i+9*j+81) % 11 == k for j in range(5))for i in range(min(n, 11))]
ans = sum(h) * (n // 11) + sum(h[i] for i in range(n % 11))
print(ans)
# Original solution
#!/usr/bin/env python
# -*- coding: utf-8 -*-
"""
input:
3
abcbdab
bdcaba
abc
abc
abc
bc

output:
4
3
2

"""
import sys
sys.setrecursionlimit(int(1e5))


def lcs(A, B):
    m, n = len(A), len(B)
    count_list = tuple([[0] * (n + 1) for _ in range(m + 1)])

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if A[i - 1] == B[j - 1]:
                count_list[i][j] = count_list[i - 1][j - 1] + 1
            else:
                count_list[i][j] = max(count_list[i - 1][j], count_list[i][j - 1])

    return count_list[m][n]


def lcs_recursive(A, B, m, n):
    if m == 0 or n == 0:
        return 0
    elif A[m - 1] == B[n - 1]:
        return 1 + lcs_recursive(A, B, m - 1, n - 1)
    else:
        return max(lcs_recursive(A, B, m, n - 1), lcs_recursive(A, B, m - 1, n))


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    pair_num = int(_input[0])

    word_list = _input[1:]
    # assert len(word_list) == 2 * pair_num
    # for k in range(0, len(word_list), 2):
    #     print(lcs(word_list[k].strip(), word_list[k + 1].strip()))

    for pair in zip(word_list[::2], word_list[1::2]):
        w1, w2 = [x.strip() for x in pair]
        l1, l2 = len(w1), len(w2)
        print((lcs_recursive(w1, w2, l1, l2)))

# Optimized solution
#!/usr/bin/env python
# -*- coding: utf-8 -*-
"""
input:
3
abcbdab
bdcaba
abc
abc
abc
bc

output:
4
3
2

"""
import sys

sys.setrecursionlimit(int(1e5))


def lcs(A, B):
    m, n = len(A), len(B)
    dp = tuple([[0] * (n + 1) for _ in range(m + 1)])
    max_l = 0
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if A[i - 1] == B[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
            max_l = max(max_l, dp[i][j])

    return max_l


def lcs_recursive(A, B, m, n):
    if m == 0 or n == 0:
        return 0
    elif A[m - 1] == B[n - 1]:
        return 1 + lcs_recursive(A, B, m - 1, n - 1)
    else:
        return max(lcs_recursive(A, B, m, n - 1), lcs_recursive(A, B, m - 1, n))


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    pair_num = int(_input[0])

    word_list = _input[1:]
    # assert len(word_list) == 2 * pair_num
    # for k in range(0, len(word_list), 2):
    #     print(lcs(word_list[k].strip(), word_list[k + 1].strip()))

    for pair in zip(word_list[::2], word_list[1::2]):
        w1, w2 = [x.strip() for x in pair]
        # l1, l2 = len(w1), len(w2)
        print((lcs(w1, w2)))
# Original solution
import sys


n = int(eval(input()))

primary = [0] * 1000
secondary = [0] * 1000


for i in range(n):
    s1 = sys.stdin.readline().strip()
    s2 = sys.stdin.readline().strip()

    len1 = len(s1)
    len2 = len(s2)

    for i in range(len1):
        primary[i] = 0
        secondary[i] = 0

    for i in range(len2):
        for j in range(len1):
            if s1[j] == s2[i]:
                matched = 1
            else:
                matched = 0

            if j == 0:
                secondary[j] = matched
            else:
                sc0 = secondary[j-1]
                pr0 = primary[j-1] + matched
                pr1 = primary[j]
                if sc0 > pr0:
                    if pr0 > pr1:
                        secondary[j] = sc0
                    elif sc0 > pr1:
                        secondary[j] = sc0
                    else:
                        secondary[j] = pr1
                else:
                    if sc0 > pr1:
                        secondary[j] = pr0
                    elif pr0 > pr1:
                        secondary[j] = pr0
                    else:
                        secondary[j] = pr1

        primary, secondary = secondary, primary

    print((primary[len1-1]))



# Optimized solution
import sys


def len_lcs(s1, s2):
    """Find length of the longest common sequence(LCS) of strings s1 and s2.
    The complexity is ~MN.

    >>> len_lcs("abc", "abc")
    3
    >>> len_lcs("abcbdaba", "bdcaba")
    5
    """
    results = [0] * len(s1)

    for i, c2 in enumerate(s2):
        sec1, pr1 = 0, 0
        for j, c1 in enumerate(s1):
            if c1 == c2:
                match = 1
            else:
                match = 0
            pr2 = results[j]
            mval = max(sec1, pr2, pr1 + match)
            results[j] = mval
            sec1, pr1 = mval, pr2

    return results[-1]


def run():
    n = int(eval(input()))
    s = []
    for line in sys.stdin:
        s.append(line.strip())
    for i in range(0, 2*n, 2):
        print((len_lcs(s[i], s[i+1])))


run()
# Original solution
import sys


def len_lcs(s1, s2):
    """Find length of the longest common sequence(LCS) of strings s1 and s2.
    The complexity is ~MN.

    >>> len_lcs("abc", "abc")
    3
    >>> len_lcs("abcbdaba", "bdcaba")
    5
    """
    results = [0] * len(s1)

    for i, c2 in enumerate(s2):
        sec1, pr1 = 0, 0
        for j, c1 in enumerate(s1):
            if c1 == c2:
                match = 1
            else:
                match = 0
            pr2 = results[j]
            mval = max(sec1, pr2, pr1 + match)
            results[j] = mval
            sec1, pr1 = mval, pr2

    return results[-1]



n = int(eval(input()))
s = []
for line in sys.stdin:
    s.append(line.strip())
for i in range(0, 2*n, 2):
    print((len_lcs(s[i], s[i+1])))





# Optimized solution
import sys


def len_lcs(s1, s2):
    """Find length of the longest common sequence(LCS) of strings s1 and s2.
    The complexity is ~MN.

    >>> len_lcs("abc", "abc")
    3
    >>> len_lcs("abcbdaba", "bdcaba")
    5
    """
    results = [0] * len(s1)

    for i, c2 in enumerate(s2):
        sec1, pr1 = 0, 0
        for j, c1 in enumerate(s1):
            pr2 = results[j]
            if c1 == c2:
                mval = pr1 + 1
            elif sec1 > pr2:
                mval = sec1
            else:
                mval = pr2

            results[j] = mval
            sec1, pr1 = mval, pr2

    return results[-1]


def run():
    n = int(eval(input()))
    s = []
    for line in sys.stdin:
        s.append(line.strip())
    for i in range(0, 2*n, 2):
        print((len_lcs(s[i], s[i+1])))

run()
# Original solution
e=input
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]
 print((len(z)))


# Optimized solution
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+=[len(z)]
print(*a,sep='\n')
# Original solution
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+=[len(z)]
print(*a,sep='\n')


# Optimized solution
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:]))
# Original solution
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+=[z]
print(('\n'.join(map(str,list(map(len,a))))))


# Optimized solution
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+=[z]
print(*map(len,a),sep='\n')
# Original solution
def lcs(X, Y):
    X = " " + X
    Y = " " + Y
    c = [[0 for j in range(len(Y))] for i in range(len(X))]
    maxl = 0
    
    for i in range(1,len(X)):
        for j in range(1,len(Y)):
            if X[i] == Y[j]:
                c[i][j] = c[i - 1][j - 1] + 1
            else:
                c[i][j] = max(c[i - 1][j], c[i][j - 1])
            maxl = max(maxl, c[i][j])
    return maxl
n = int(input())
 
for i in range(n):
    s1 = input()
    s2 = input()
    print(lcs(s1, s2))

# Optimized solution
def lcs(X, Y):
    X = " " + X
    Y = " " + Y
    #c = [[0 for j in range(len(Y))] for i in range(len(X))]
    c = [[0] * len(Y) for i in range(len(X))]
    maxl = 0
    
    for i in range(1,len(X)):
        for j in range(1,len(Y)):
            if X[i] == Y[j]:
                c[i][j] = c[i - 1][j - 1] + 1
            else:
                c[i][j] = max(c[i - 1][j], c[i][j - 1])
            maxl = max(maxl, c[i][j])
    return maxl
n = int(input())
 
for i in range(n):
    s1 = input()
    s2 = input()
    print(lcs(s1, s2))
# Original solution
def lcs(X, Y):
    X = " " + X
    Y = " " + Y
    #c = [[0 for j in xrange(len(Y))] for i in xrange(len(X))]
    c = [[0] * len(Y) for i in range(len(X))]
    maxl = 0
    
    for i in range(1,len(X)):
        for j in range(1,len(Y)):
            if X[i] == Y[j]:
                c[i][j] = c[i - 1][j - 1] + 1
            else:
                c[i][j] = max(c[i - 1][j], c[i][j - 1])
            maxl = max(maxl, c[i][j])
    return maxl
n = int(input())
 
for i in range(n):
    s1 = input()
    s2 = input()
    print(lcs(s1, s2))

# Optimized solution
def lcs(X, Y):
    #X = " " + X
    #Y = " " + Y
    #c = [[0 for j in xrange(len(Y))] for i in xrange(len(X))]
    c2 = [0 for i in range(len(Y) + 1)]
    #maxl = 0
     
    for i in range(len(X)):
        c1 = c2 + []
        for j in range(len(Y)):
            if X[i] == Y[j]:
                c2[j + 1] = c1[j] + 1
            elif c2[j + 1] < c2[j]:
                c2[j + 1] = c2[j]
    return c2[-1]
n = int(input())
  
for i in range(n):
    s1 = input()
    s2 = input()
    print(lcs(s1, s2))