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
/*
    Anuraj Agarwal
*/
#include<bits/stdc++.h>
#include<chrono>

using namespace std;
using namespace chrono;

#define PI 3.1415926535897932384626
#define sp(x,y)                     fixed<<setprecision(y)<<x
#define mk(arr,n,type)              type *arr=new type[n]; // dynamic allocation of memory
#define del(arr)                    delete []arr;           // deletion of allocated memory
// const int m = 1'000'000'007;

#define fo(i, n) for(i=0; i<n; i++)
#define Fo(i,k,n) for(i=k;k<n?i<n:i>n;k<n?i+=1:i-=1)
#define ll long long
#define pb push_back
#define F first
#define S second
#define vbe(x) x.begin(), x.end()
#define sortvbe(x) sort(vbe(x))
#define deb(x) cout << #x << " = " << x << endl; //to check the values

inline void swap(int &a, int &b)
{
    int temp = a;
    a = b;
    b = temp;
}
inline int modulo(int a, int b)
{
    return (b + (a % b)) % b;
}
inline ll pow_mod(ll e, ll p, ll m )
{
    ll res = 1, temp = e;
    while(p)
    {
        if(p & 1)res = res * temp % m;
        temp = temp * temp % m;
        p >>= 1;
    }
    return res;
}
inline ll expo_mod(ll e, ll p, ll m)
{
    if(p == 0)return (1);
    ll ans = expo_mod(e, p / 2, m);
    ans = ((ans % m) * (ans % m)) % m;
    if(p % 2 != 0)ans = ((e % m) * (ans % m)) % m;
    return ans % m;
}
inline ll expo(ll e, ll p)
{
    if(p == 0)return (1);
    ll ans = expo(e, p / 2);
    ans = (ans) * (ans);
    if(p % 2 != 0)ans = (e) * (ans);
    return ans;
}
inline ll com_wd_m(ll n, ll r, ll m)
{
    ll p = 1, d = 1;
    if(r == 0 or r == n )return(1);
    if(r == 1 )return (n % m);
    r = min(r, n - r);
    for(ll i = 0; i < r; i++)
    {
        p = ((p % m) * ((n % m) - (i % m)) % m) % m;
        p = ((p % m) * (expo_mod((i + 1), m - 2, m) % m)) % m;
    }
    return (p % m);
}
inline ll com(ll n, ll k)
{
    ll res = 1;
    if (k > n - k)
        k = n - k;
    for (ll i = 0; i < k; ++i)
    {
        res *= (n - i);
        res /= (i + 1);
    }
    return res;
}
inline ll fact(ll n)
{
    return (n == 1 || n == 0) ? 1 : n * fact(n - 1);
}
inline ll fact_mod(ll n, ll x, ll m)
{
    if(n == x) return 1;
    return (n == 1 || n == 0) ? 1 : ((n % m) * (fact((n - 1) % m)) % m) % m;
}
vector<ll> prime(ll n)
{
    ll *arr = new ll[n + 1]();
    vector<ll> vect;
    for (ll i = 2; i <= n; i++)
    {
        if (arr[i] == 0)
        {
            vect.push_back(i);
            for (ll j = 2 * i; j <= n; j += i)
                arr[j] = 1;
        }
    }
    return vect;
}
const ll MOD = 1e9 + 7;
// ll InvFac[200000 + 1];
// ll InvNum[200000 + 1];
// ll Fac[200000 + 1];
// void InvNumfunc()
// {
//     InvNum[200000]=pow_mod(Fac[200000],MOD-2,MOD);
//     for (ll i = 199999; i >=0; i--)
//         InvNum[i] = InvNum[i+1] * (i+1) % MOD;
// }
// void InvFacfunc()
// {
//     InvFac[0] = InvFac[1] = 1;

//     for (ll i = 2; i <= 200000; i++)
//         InvFac[i] = (InvNum[i] * InvFac[i - 1]) % MOD;
// }
// void Facfunc()
// {
//     Fac[0] = 1;
//     for (int i = 1; i <= 200000; i++)
//     {
//         Fac[i] = (Fac[i - 1] * i) % MOD;
//     }
// }
void A_A()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}
ll num;
void solve()
{
   string s1,s2;
   cin>>s1>>s2;
   map<string,ll> strings;
   string s;
   for(int i=0;i<s1.size();i++){
    for(int j=i;j<s1.size();j++){
        s.pb(s1[j]);
        strings[s]=(ll)s.size();
    }
    s.clear();
   }
   s.clear();
   vector<ll> sz;
   for(int i=0;i<s2.size();i++){
    for(int j=i;j<s2.size();j++){
        s.pb(s2[j]);
        if(strings[s]!=(ll)0){
            sz.pb(strings[s]);
        }
    }
    s.clear();
   }
   if(sz.size()==0){
    cout<<(ll)s1.size()+(ll)s2.size()<<endl;
    return;
   }
   sortvbe(sz);
   cout<<(ll)s1.size()+(ll)s2.size()-(ll)(2*sz[sz.size()-1])<<endl;

}
int main()
{
    A_A();
    ll t = 1;
    cin >> t;
    while(t--)
    {
        solve();
    }
    cerr << "Itna time laga hai dekh lo : " << (float)clock() / CLOCKS_PER_SEC << " secs" << endl;
    return 0;
}


