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
/**
 *    author:  ChristianGrey2k2
 *    created: ?.?.? ?:?:?
**/
#include<bits/stdc++.h>

using namespace std;

#define FOR(x,a,b) for (ll x=a;x<=b;x++)
#define FOD(x,a,b) for (ll x=a;x>=b;x--)
#define rep(x,a,b) for (ll x=a;x<b;x++)
#define red(x,a,b) for (ll x=a;x>b;x--)

typedef long long ll;
typedef float f;
const ll maxn=1e6+5;
ll a[maxn];
ll c[maxn];
bool Prime[maxn];


///......MERGE SORT......///
void Merge(ll a[],ll l,ll m,ll r)
{
    ll n1=m-l+1;
    ll n2=r-m;
    ll L[n1];ll R[n2];
    for(ll i=0;i<n1;i++)
        L[i]=a[l+i];
    for(ll i=0;i<n2;i++)
        R[i]=a[m+1+i];
    ll i=0;ll j=0;ll k=l;
    while(i<n1&&j<n2)
    {
        if(L[i]<=R[j])
        {
            a[k]=L[i];
            i++;
        }
        else
        {
            a[k]=R[j];
            j++;
        }
        k++;
    }
    while(i<n1)
    {
        a[k]=L[i];
        i++;
        k++;
    }
    while(j<n2)
    {
        a[k]=R[j];
        j++;
        k++;
    }
}

void MergeSort(ll a[],ll l,ll r)
{
    if(l>=r) return;
    ll m=(l+r)/2;
    MergeSort(a,l,m);
    MergeSort(a,m+1,r);
    Merge(a,l,m,r);
}

///......BINARY SEARCH......///
ll Search(ll a[],ll l,ll r,ll n)
{
    if(l<=r)
    {
        ll m=(l+r)/2;
        if(a[m]<=n&&a[m+1]>n) return(m);
        else if(a[m]>n) return Search(a,l,m-1,n);
        else if(a[m]<n) return Search(a,m+1,r,n);
    }
    else return 0;
}


void Swap(ll *a,ll *b)
{
    ll temp=0;
    temp=*a;
    *a=*b;
    *b=temp;
}

void Insert(ll &n,ll a[],ll pos,ll x)
{
	for(ll i=n;i>pos;i--)
	{
        a[i]=a[i-1];
    }
    n++;
    a[pos]=x;
}

void Delete(ll &n,ll a[],ll pos)
{
	for(ll i=pos;i<n-1;i++)
	{
        a[i]=a[i+1];
	}
	n--;
}

ll gcd(ll a,ll b){return ((b==0)?a:gcd(b,a%b));}
int lcm(int a,int b){return a*b/gcd(a,b);}

float mu(ll a,ll b)
{
    float sum=a;
    b--;
    while(b--)
    {
        sum*=a;
    }
    return sum;
}

void snt(){
    for(ll i=0;i<=maxn;i++)
    {
        Prime[i]=true;
    }
    Prime[0]=false;Prime[1]=false;
    for(ll i=2;i*i<=maxn;i++)
    {
        if(Prime[i]==true)
        {
            for(ll j=i*i;j<=maxn;j+=i)
            {
                Prime[j]=false;
            }
        }
    }
}

ll giaithua(ll n)
{
    if (n == 1)
        return 1;
    return n * giaithua(n - 1);
}

ll giao(ll a,ll b,ll c,ll d)
{
    ll s1=abs(a-b);
    ll s2=abs(c-d);
    ll _max=max({a,b,c,d});
    ll _min=min({a,b,c,d});
    ll res=_max-_min;
    if(res>s1+s2) return 0;
    return s1+s2-res;
}

ll Check[256];

/*  (a+b)%c=(a%c+b%c)%c
    (a-b)%C=(a%c-b%c+c^2)%c
    (a.b)%c=(a%c.b%c)%c
    (a/b)%c=(a%c.b^(c-2)%c)%c
*/

void solve(){

    string s1,s2; cin>>s1>>s2;
    ll _max=0; ll cnt=0; ll _max2=0;
    rep(i,0,s1.size())
    {
        ll m=i;
        rep(j,0,s2.size())
        {
            ll n=j;
            if(s1[i]==s2[j])
            {
                m=i;
                string z1="";
                z1+=s1[i];
                string z2="";
                z2+=s2[j];
                while(z1==z2&&(m<s1.size()&&n<s2.size()))
                {
                    cnt++;
                    z1+=s1[m+1];
                    z2+=s2[n+1];
                    m++;
                    n++;

                }
                _max=max(_max,cnt);
                cnt=0;
            }
    }
    }
    FOD(i,s1.size()-1,0)
    {
        ll m=i;
        FOD(j,s2.size()-1,0)
        {
            ll n=j;
            if(s1[i]==s2[j])
            {
                m=i;
                string q1="";
                q1+=s1[i];
                string q2="";
                q2+=s2[j];
                while(q1==q2&&(m>=0&&n>=0))
                {
                    cnt++;
                    q1+=s1[m-1];
                    q2+=s2[n-1];
                    m--;
                    n--;
                }
                _max2=max(_max2,cnt);
                cnt=0;
            }
    }
    }
    ll _maxx=max(_max,_max2);
    cout<<s1.size()+s2.size()-_maxx*2<<endl;

}

int main()
{
    ///:::::::::REAL CODE:::::::::///
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie();
    /////////////////////////

    ll t; cin>>t;
    while(t--)
    {
        solve();
    }


    //cout<<fixed<<setprecision(15)<<(a*b)/(a+b)<<endl;///
    return 0;
}

    ///.VECTOR.///
/*  vector<ll> v;
    ll n;
    cin>>n;
    v.resize(n);
    for(ll i=0;i<n;i++)
    {
        cin>>v[i];
    }
    for(ll i=0;i<n;i++)
    {
        cout<<v.at(i)<<" ";
    }
*/

    ///......two pointer......///
/*  ll _start=1;ll _end=1;ll cnt=0;
    for(_end=1;_end<=n;_end++)
    {
        while(cnt==k)
        {
            sum-=a[_start];
            _start++;
            cnt--;
        }
        sum+=a[_end];
        cnt++;
        _max=max(sum,_max);
    }
    cout<<_max+_sum;
*/

    /// Sieve of Eratosthenes///
/*    for(ll i=0;i<=maxn;i++)
    {
        Prime[i]=true;
    }
    Prime[0]=false;Prime[1]=false;
    for(ll i=2;i*i<=maxn;i++)
    {
        if(Prime[i]==true)
        {
            for(ll j=i*i;j<=maxn;j+=i)
            {
                Prime[j]=false;
            }
        }
    }
*/

    /// ...ABBA...///
/*  ll m,n;
    cin>>m>>n;
    char s[m][n];
    ll cnt=0;
    for(ll i=0;i<m;i++)
    {
        for(ll j=0;j<n;j++)
        {
           cin>>s[i][j];
           if(s[i][j]=='.')
           {
                if((i+j)&1)
                    s[i][j] = 'W';
                else
                    s[i][j] = 'B';
           }
        }
    }
    for(ll i=0;i<m;i++)
    {
        for(ll j=0;j<n;j++)
        {
           cout<<s[i][j];
        }
        cout<<endl;
    }
    ///(i+j) & 1 will evaluate to true when i+j is odd and false when i+j is even.
*/
