for _ in[0]*int(eval(input())):

 X,z=eval(input()),[]

 for y in eval(input()):

  s=i=0

  for k in z:

   t=X.find(y,s)+1

   if t<1:break

   z[i]=min(t,k)

   s=k;i+=1

  else:

   t=X.find(y,s)+1

   if t:z+=[t]

 print((len(z)))

for _ in[0]*int(eval(input())):

 X,z=eval(input()),[]

 for y in eval(input()):

  s=i=0

  for k in z:

   t=X.find(y,s)+1

   if not t: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)))

for _ in [0] * int(eval(input())):
    X, z = eval(input()), []
    for y in eval(input()):
        s = i = 0
        for k in z:
            t = X.find(y, s) + 1
            if t < 1:
                break
            z[i] = min(t, k)
            s = k
            i += 1
        else:
            t = X.find(y, s) + 1
            if t:
                z += [t]
    print((len(z)))

for _ in [0] * int(eval(input())):
    X, z = eval(input()), []
    for y in eval(input()):
        s = i = 0
        for k in z:
            t = X.find(y, s) + 1
            if not t:
                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)))

-            if t < 1: +            if not t: -            z[i] = min(t, k) +            if t < k: +                z[i] = t