Buggy python submission (verdict: Time Limit Exceeded):
q = int(input())

l = []
x = ""
y = ""
def lcs(yIndex, xIndex):
    global l, x, y
    if xIndex < 0 or yIndex < 0:
        return 0
    elif l[yIndex][xIndex] != -1:
        return l[yIndex][xIndex]
    elif x[xIndex] == y[yIndex]:
        return 1 + lcs(yIndex - 1, xIndex - 1)
    else:
        return max(lcs(yIndex, xIndex - 1), lcs(yIndex - 1, xIndex))

for i in range(q):
    x = input()
    y = input()

    l = [[-1] * len(x) for j in range(len(y))]

    for j in range(len(y)):
        for k in range(len(x)):
            l[j][k] = lcs(j, k)

    print(l[len(y)- 1][len(x) - 1])


Fixed submission:
q = int(input())

for i in range(q):
    x = input()
    y = input()
 
    l = []
    for j, s in enumerate(x):
        l.append([])
        l[j].append(-1)
        if j == 0:
            endPos = y.find(s)
            if endPos != -1: 
                l[j].append(endPos)
        else:
            for k, t in enumerate(l[j - 1][:-1]):
                endPos = y.find(s, t + 1)
                if endPos != -1:
                    l[j].append(min(endPos, l[j - 1][k + 1]))
                else:
                    l[j].append(l[j - 1][k + 1])
            endPos = y.find(s, l[j - 1][-1] + 1)
            if endPos != -1:
                l[j].append(endPos)

    print(len(l[-1]) - 1)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(100000)
q = int(input())

l = []
x = ""
y = ""
def lcs(yIndex, xIndex):
    global l, x, y
    if xIndex < 0 or yIndex < 0:
        return 0
    elif x[xIndex] == y[yIndex]:
        return 1 + lcs(yIndex - 1, xIndex - 1)
    else:
        return max(lcs(yIndex, xIndex - 1), lcs(yIndex - 1, xIndex))

for i in range(q):
    x = input()
    y = input()

    print(lcs(len(y) - 1, len(x) - 1))


Fixed submission:
q = int(input())

for i in range(q):
    x = input()
    y = input()
 
    l = []
    for j, s in enumerate(x):
        l.append([])
        l[j].append(-1)
        if j == 0:
            endPos = y.find(s)
            if endPos != -1: 
                l[j].append(endPos)
        else:
            for k, t in enumerate(l[j - 1][:-1]):
                endPos = y.find(s, t + 1)
                if endPos != -1:
                    l[j].append(min(endPos, l[j - 1][k + 1]))
                else:
                    l[j].append(l[j - 1][k + 1])
            endPos = y.find(s, l[j - 1][-1] + 1)
            if endPos != -1:
                l[j].append(endPos)

    print(len(l[-1]) - 1)

Buggy python submission (verdict: Time Limit Exceeded):
q = int(input())

l = []
x = ""
y = ""
"""
def lcs(yIndex, xIndex):
    global l, x, y
    if xIndex == 0 and yIndex == 0:
        return 0
    elif xIndex == 0:
        return l[yIndex - 1][0]
    elif yIndex == 0:
        return l[0][xIndex - 1]
    elif x[xIndex] == y[yIndex]:
        return 1 + l[yIndex - 1][xIndex - 1]
    else:
        if l[yIndex][xIndex - 1] > l[yIndex - 1][xIndex]:
            return l[yIndex][xIndex - 1]
        else:
            return l[yIndex - 1][xIndex]
        #return max(l[yIndex][xIndex - 1], l[yIndex - 1][xIndex])
 """
for i in range(q):
    x = input()
    y = input()
 
    yLen = len(y)
    xLen = len(x)
    l = [[0] * xLen for j in range(yLen)]

    for j in range(yLen):
        for k in range(xLen):
            if k == 0 and j == 0:
                if x[k] == y[j]:
                    l[j][k] = 1
                else:
                    l[j][k] = 0
            elif k == 0:
                if x[k] == y[j]:
                    l[j][k] = 1
                else:
                    l[j][k] = l[j - 1][k]
            elif j == 0:
                if x[k] == y[j]:
                    l[j][k] = 1
                else:
                    l[j][k] = l[j][k - 1]
            elif x[k] == y[j]:
                l[j][k] = 1 + l[j - 1][k - 1]
            else:
                if l[j][k - 1] > l[j - 1][k]:
                    l[j][k] = l[j][k - 1]
                else:
                    l[j][k] = l[j - 1][k]
            #l[j][k] = lcs(j, k)
 
    print(l[yLen- 1][xLen - 1])



Fixed submission:
q = int(input())

for i in range(q):
    x = input()
    y = input()
 
    l = []
    for j, s in enumerate(x):
        l.append([])
        l[j].append(-1)
        if j == 0:
            endPos = y.find(s)
            if endPos != -1: 
                l[j].append(endPos)
        else:
            for k, t in enumerate(l[j - 1][:-1]):
                endPos = y.find(s, t + 1)
                if endPos != -1:
                    l[j].append(min(endPos, l[j - 1][k + 1]))
                else:
                    l[j].append(l[j - 1][k + 1])
            endPos = y.find(s, l[j - 1][-1] + 1)
            if endPos != -1:
                l[j].append(endPos)

    print(len(l[-1]) - 1)

Buggy python submission (verdict: Time Limit Exceeded):
q = int(input())

l = []
x = ""
y = ""

for i in range(q):
    x = input()
    y = input()
 
    yLen = len(y)
    xLen = len(x)
    l = [[0] * xLen for j in range(yLen)]

    for j in range(yLen):
        for k in range(xLen):
            if k == 0 and j == 0:
                if x[k] == y[j]:
                    l[j][k] = 1
                else:
                    l[j][k] = 0
            elif k == 0:
                if x[k] == y[j]:
                    l[j][k] = 1
                else:
                    l[j][k] = l[j - 1][k]
            elif j == 0:
                if x[k] == y[j]:
                    l[j][k] = 1
                else:
                    l[j][k] = l[j][k - 1]
            elif x[k] == y[j]:
                l[j][k] = 1 + l[j - 1][k - 1]
            else:
                if l[j][k - 1] > l[j - 1][k]:
                    l[j][k] = l[j][k - 1]
                else:
                    l[j][k] = l[j - 1][k]
 
    print(l[yLen- 1][xLen - 1])



Fixed submission:
q = int(input())

for i in range(q):
    x = input()
    y = input()
 
    l = []
    for j, s in enumerate(x):
        l.append([])
        l[j].append(-1)
        if j == 0:
            endPos = y.find(s)
            if endPos != -1: 
                l[j].append(endPos)
        else:
            for k, t in enumerate(l[j - 1][:-1]):
                endPos = y.find(s, t + 1)
                if endPos != -1:
                    l[j].append(min(endPos, l[j - 1][k + 1]))
                else:
                    l[j].append(l[j - 1][k + 1])
            endPos = y.find(s, l[j - 1][-1] + 1)
            if endPos != -1:
                l[j].append(endPos)

    print(len(l[-1]) - 1)

Buggy python submission (verdict: Time Limit Exceeded):
q = int(input())

l = []
x = ""
y = ""

for i in range(q):
    x = input()
    y = input()
 
    yLen = len(y)
    xLen = len(x)
    l = [[0] * (xLen + 1) for j in range(yLen + 1)]

    for j in range(1, yLen + 1):
        for k in range(1, xLen + 1):
            if x[k - 1] == y[j - 1]:
                l[j][k] = 1 + l[j - 1][k - 1]
            else:
                if l[j][k - 1] > l[j - 1][k]:
                    l[j][k] = l[j][k - 1]
                else:
                    l[j][k] = l[j - 1][k]
 
    print(l[yLen][xLen])



Fixed submission:
q = int(input())

for i in range(q):
    x = input()
    y = input()
 
    l = []
    for j, s in enumerate(x):
        l.append([])
        l[j].append(-1)
        if j == 0:
            endPos = y.find(s)
            if endPos != -1: 
                l[j].append(endPos)
        else:
            for k, t in enumerate(l[j - 1][:-1]):
                endPos = y.find(s, t + 1)
                if endPos != -1:
                    l[j].append(min(endPos, l[j - 1][k + 1]))
                else:
                    l[j].append(l[j - 1][k + 1])
            endPos = y.find(s, l[j - 1][-1] + 1)
            if endPos != -1:
                l[j].append(endPos)

    print(len(l[-1]) - 1)