#include<stdio.h>
#include<string.h>
#define MAXN 0x7FFFFFF

int Q,n,m,f[3001][3001];

char s1[5000],s2[5000];

inline int min(int a,int b)
{
	return a<b?a:b;
}

int main()
{
	freopen("dna.in","r",stdin);
	freopen("dna.out","w",stdout);
	int i,j;
	scanf("%d\n",&Q);
	while(Q--)
	{
		memset(f,0,sizeof(f));
		memset(s1,0,sizeof(s1));
		memset(s2,0,sizeof(s2));
		scanf("%s\n%s\n",s1+1,s2+1);
		s1[0]='a';s2[0]='b';
		m=strlen(s1+1);
		n=strlen(s2+1);
		for(i=1;i<=n;i++)
		{
			f[i][0]=MAXN;
			for(j=1;j<=m;j++)
			{
				if(s2[i]==s1[j])
				{
					if(s2[i-1]==s1[j-1])
					{
						if(j==m)
							f[i][j]=min(f[i-1][j-1]-1,f[i][j-1]);
						else
							f[i][j]=min(f[i-1][j-1],f[i][j-1]);
					}
					else
					{
						if(j==1&&j==m)
							f[i][j]=f[i-1][j-1];
						else if(j==1)
							f[i][j]=f[i-1][j-1]+1;
						else if(j==m&&i==1)
							f[i][j]=min(f[i-1][j-1]+1,f[i][j-1]);
						else if(j==m)
							f[i][j]=min(f[i-1][j-1]+2,f[i][j-1]);
						else if(i==1)
							f[i][j]=min(f[i-1][j-1]+2,f[i][j-1]);
						else
							f[i][j]=min(f[i-1][j-1]+3,f[i][j-1]);
					}
				}
				else
				{
					f[i][j]=f[i][j-1];
				}
			}
		}
		if(f[n][m]>=100000000)
			f[n][m]=-1;
		printf("%d\n",f[n][m]);
	}
	return 0;
}