using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Text;
using System.Text.RegularExpressions;
using static System.Math;

namespace CsharpSpiral {
    partial class Program {
        static void Main(string[] args) {
            var sw = new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
            Console.SetOut(sw);
            new Program().Solve(new ConsoleInput(Console.In, ' '));
            Console.Out.Flush();
        }
        public void Solve(ConsoleInput cin) {
            var n = cin.ReadInt;
            for(int i = 0; i < n; i++) {
                var X = cin.ReadLine;
                var Y = cin.ReadLine;
                Console.WriteLine(LongestCommonSubsequence(X, Y));
            }
        }
        public int LongestCommonSubsequence(string x,string y) {
            var M = x.Length;
            var N = y.Length;
            var dp = new int[M, N];
            dp[0, 0] = x[0] == y[0] ? 1 : 0;
            for(int j = 1; j < N; j++) {
                dp[0, j] = dp[0, j - 1] > 0 ? dp[0, j - 1] : x[0] == y[j] ? 1 : 0;
            }
            for(int i = 1; i < M; i++) {
                dp[i, 0] = dp[i - 1, 0] > 0 ? dp[i - 1, 0] : x[i] == y[0] ? 1 : 0;
            }
            for(int i = 1; i < M; i++) {
                for(int j = 1; j < N; j++) {
                    if(x[i] == y[j]) dp[i, j] = dp[i - 1, j - 1] + 1;
                    else dp[i, j] = Max(dp[i - 1, j], dp[i, j - 1]);
                }
            }
            return dp[M - 1, N - 1];
        }
    }

    static class ExtendClass {
        public static string Join<T>(this IEnumerable<T> X, string separator = " ") => string.Join(separator, X);
    }

    class ConsoleInput {
        private readonly TextReader _stream;
        private readonly char _separator = ' ';
        private readonly Queue<string> inputStream;
        public ConsoleInput(TextReader stream, char separator = ' ') {
            this._separator = separator;
            this._stream = stream;
            inputStream = new Queue<string>();
        }
        public string Read {
            get {
                if(inputStream.Count != 0) return inputStream.Dequeue();
                string[] tmp = _stream.ReadLine().Split(_separator);
                for(int i = 0; i < tmp.Length; ++i)
                    inputStream.Enqueue(tmp[i]);
                return inputStream.Dequeue();
            }
        }
        public string ReadLine { get { return _stream.ReadLine(); } }
        public int ReadInt { get { return int.Parse(Read); } }
        public long ReadLong { get { return long.Parse(Read); } }
        public double ReadDouble { get { return double.Parse(Read); } }
        public string[] ReadStrArray(long N) {
            var ret = new string[N];
            for(long i = 0; i < N; ++i)
                ret[i] = Read;
            return ret;
        }
        public int[] ReadIntArray(long N) { var ret = new int[N]; for(long i = 0; i < N; ++i) ret[i] = ReadInt; return ret; }
        public long[] ReadLongArray(long N) { var ret = new long[N]; for(long i = 0; i < N; ++i) ret[i] = ReadLong; return ret; }
        public double[] ReadDoubleArray(long N) { var ret = new double[N]; for(long i = 0; i < N; ++i) ret[i] = ReadDouble; return ret; }
    }

}



Measured memory_bytes: 35416