#include<bits/stdc++.h>
#define ll long long
using namespace std;

string A,B;  // 存储输入的两个字符串
ll dp[1000][1000];  // DP数组，dp[i][j]表示A前i个字符转B前j个字符的最小操作数
ll T;  

signed main(){
    cin>>T;  // 读取测试用例数量
    while(T--)  // 处理每个测试用例
    {
        cin>>A>>B;  // 读取两个字符串
        ll Alen=A.size();  // 字符串A的长度
        ll Blen=B.size();  // 字符串B的长度
        
        // 初始化边界条件：
        // 将A前i个字符转为空串需要i次删除操作
        for(int i=1;i<=Alen;i++) dp[i][0]=i;
        // 将空串转为B前j个字符需要j次插入操作
        for(int i=1;i<=Blen;i++) dp[0][i]=i;
        
        for(int i=1;i<=Alen;i++)  // 遍历A的每个字符
        {
            for(int j=1;j<=Blen;j++)  // 遍历B的每个字符
            {
                if(A[i-1]==B[j-1])  // 当前字符相同
                {
                    // 无需操作，继承左上角的值
                    dp[i][j]=dp[i-1][j-1];    
                }
                else  // 当前字符不同
                {
                    // 取三种操作的最小值加1：
                    // 1. dp[i-1][j]: 删除A[i-1]
                    // 2. dp[i][j-1]: 在A中插入B[j-1]
                    // 3. dp[i-1][j-1]: 替换A[i-1]为B[j-1]
                    dp[i][j]=min(dp[i-1][j],min(dp[i][j-1],dp[i-1][j-1]))+1;
                }
            }    
        }
        // 输出最终结果：将整个A转为整个B的最小操作数
        cout<<dp[Alen][Blen];
    }
    
    return 0;
}