You are given the strings a and b, consisting of lowercase Latin letters. You can do any number of the following operations in any order: 

  * if |a| > 0 (the length of the string a is greater than zero), delete the first character of the string a, that is, replace a with a_2 a_3 … a_n; 
  * if |a| > 0, delete the last character of the string a, that is, replace a with a_1 a_2 … a_{n-1}; 
  * if |b| > 0 (the length of the string b is greater than zero), delete the first character of the string b, that is, replace b with b_2 b_3 … b_n; 
  * if |b| > 0, delete the last character of the string b, that is, replace b with b_1 b_2 … b_{n-1}. 



Note that after each of the operations, the string a or b may become empty.

For example, if a="hello" and b="icpc", then you can apply the following sequence of operations: 

  * delete the first character of the string a ⇒ a="ello" and b="icpc"; 
  * delete the first character of the string b ⇒ a="ello" and b="cpc"; 
  * delete the first character of the string b ⇒ a="ello" and b="pc"; 
  * delete the last character of the string a ⇒ a="ell" and b="pc"; 
  * delete the last character of the string b ⇒ a="ell" and b="p". 



For the given strings a and b, find the minimum number of operations for which you can make the strings a and b equal. Note that empty strings are also equal.

Input

The first line contains a single integer t (1 ≤ t ≤ 100). Then t test cases follow.

The first line of each test case contains the string a (1 ≤ |a| ≤ 20), consisting of lowercase Latin letters.

The second line of each test case contains the string b (1 ≤ |b| ≤ 20), consisting of lowercase Latin letters.

Output

For each test case, output the minimum number of operations that can make the strings a and b equal.

Example

Input


5
a
a
abcd
bc
hello
codeforces
hello
helo
dhjakjsnasjhfksafasd
adjsnasjhfksvdafdser


Output


0
2
13
3
20
#include<bits/stdc++.h>
using namespace std;
#define ll long long 
#define pb push_back
#define mp make_pair
#define fi first
#define se second
//ll m=1e9+7;
/*ll exp(ll x,ll y)
{
	if(y==0)
	return 1;
	else if(y==1)
	return x%m;
	ll z=exp(x,y/2)%m;
	if(y%2==0)
	return ((z)*(z))%m;
	else
	return (((z*z)%m)*x)%m;
}*/
/*int a[105];
//vector < long long  > v;
void sieve()
{
	long long  i=0,j=0;
	for(i=1;i<=105;i+=2)
	{a[i]=1;a[i+1]=0;}
	a[1]=0;
	a[2]=1;
	a[0]=0;
	//v.push_back(2);
	for(i=3;i<=105;i+=2)
	{
		if(a[i]==1)
		{
			for(j=i*i;j<=105;j+=2*i)
			a[j]=0;
			
		//	v.push_back(i);
		}
	}
}*/
/*long long ncr(long long n,long long k)
{
	if(k==0)
	return 1;
	if(k>n-k)
	k=n-k;
	
	long long a=1,b=1,d;
	while(k)
	{
		a*=n;
		b*=k;
		d=__gcd(a,b);
		a/=d;
		b/=d;
		n--;k--;
	}
	return a;
}*/
ll max( ll x, ll y)
{
	if(x>=y)return x;
	return y;
}
ll min( ll x, ll y)
{
	if(x>y)return y;
	return x;
}
/*int p(string s)
{
	int i;
	for(i=0;i<s.size();i++)
	{
		if(s[i]!=s[s.size()-1-i])return 0;
	}return 1;
}*/
/*bool compare(vector<int>  a,vector<int> b)
{
	return b.size()>a.size();
}*/
/*struct node{
	ll c1=0,c2=0,p=1e10;
};
const ll s=1e5+10;
node x[4*s];
pair<ll,ll> a[s];
void cr(ll l,ll r,ll z)
{
	if(l==r)
	{
		x[z].c1=a[l].fi;
		x[z].c2=a[l].fi;
		x[z].p=a[l].se;		
		return ;
	}
	cr(l,(l+r)/2,2*z+1);
	cr((l+r)/2+1,r,2*z+2);
	x[z].c1=x[2*z+1].c1;
	x[z].c2=x[2*z+2].c2;
	x[z].p=min(x[2*z+1].p,x[2*z+2].p);
	return;
}
/*void up(ll l,ll k,ll ss,ll se,ll z)
{
	if(ss>l||se<l)return;
	if(ss==se)
	{
		x[z].s=k;
		x[z].ls=max((ll)0,k);
		x[z].rs=max((ll)0,k);
		return;
	}
	up(l,k,ss,(ss+se)/2,2*z+1);
	up(l,k,(ss+se)/2+1,se,2*z+2);
	x[z].s=x[2*z+1].s+x[2*z+2].s;
	x[z].rs=max((ll)0,max(x[2*z+2].rs,x[2*z+2].s+x[2*z+1].rs));
	x[z].ls=max((ll)0,max(x[2*z+1].ls,x[2*z+1].s+x[2*z+2].ls));
	return ;
	
}
node in(ll l,ll r,ll ss,ll se,ll z)
{
	if(x[z].c1>r||x[z].c2<l)
	{
		node p;
		return p;
	}
	if(x[z].c1>=l && x[z].c2<=r)return x[z];
	node i,j,y;
	i=in(l,r,ss,(ss+se)/2,2*z+1);
	j=in(l,r,(ss+se)/2+1,se,2*z+2);
	y.c1=i.c1;
	y.c2=j.c2;
	y.p=min(i.p,j.p);
	return y;		
}*/
struct compare {
    bool operator()( pair<ll,pair<ll,ll> > const& p1, pair<ll,pair<ll,ll> > const& p2)
    {
        // return "true" if "p1" is ordered 
        // before "p2", for example:
        if(p1.fi < p2.fi)return 1;
        else if(p1.fi==p2.fi)return p1.se.se>p2.se.se;
        else return 0;
    }
};
int main()
{
	ios_base::sync_with_stdio(false);
	cout.tie(NULL);
	cin.tie(NULL);
	ll t;
	cin>>t;
	while(t--)
	{
		string a,b,s="";
		cin>>a>>b;
		ll m=1e18,i,j;
		for(i=0;i<a.size();i++)
		{s="";
			for(j=i;j<a.size();j++)
			{
				s+=a[j];
				if(b.find(s)!=string::npos)m=min(a.size()+b.size()-2*s.size(),m);
			}
		}if(m==1e18)cout<<a.size()+b.size()<<endl;
		else cout<<m<<endl;
	}
return 0;
}
