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
import java.util.*;
import java.lang.*;
import java.io.*;



public class cf710 {

//HashMap<Integer,Integer> hm=new HashMap<>();
//ArrayList<Integer> list=new ArrayList<>();
//HashSet<Integer> hs=new HashSet<>();
//Stack<Integer> st=new Stack<>();
//Queue<Integer> q=new LinkedList<>();
//PriorityQueue<Integer> pq=new PriorityQueue<>();
// static ArrayList<ArrayList<Integer>> gp=new ArrayList<>();
//int[] arr=new int[n];
//System.out.println("YES");
//1 hr- atleast 2 qs d-2
//Mt_do 3 qs d-2  
//Mt_do 4 qs d-3
//StringBuilder sb=new StringBuilder();

    //Q-3  V.V.Imp
    public static int LCSubStr(char X[], char Y[],int m, int n){
    // Create a table to store
    // lengths of longest common
    // suffixes of substrings.
    // Note that LCSuff[i][j]
    // contains length of longest
    // common suffix of
    // X[0..i-1] and Y[0..j-1].
    // The first row and first
    // column entries have no
    // logical meaning, they are
    // used only for simplicity of program
    int LCStuff[][] = new int[m + 1][n + 1];

    // To store length of the longest
    // common substring
    int result = 0;

    // Following steps build
    // LCSuff[m+1][n+1] in bottom up fashion
    for (int i = 0; i <= m; i++)
    {
    for (int j = 0; j <= n; j++)
    {
    if (i == 0 || j == 0)
    LCStuff[i][j] = 0;
    else if (X[i - 1] == Y[j - 1])
    {
    LCStuff[i][j]
    = LCStuff[i - 1][j - 1] + 1;
    result = Integer.max(result,
                    LCStuff[i][j]);
    }
    else
    LCStuff[i][j] = 0;
    }
    }
    return result;
    }


    public static int longComSubString(String x,String y){
        int n=x.length(),m=y.length();
        int[][] mat=new int[n+1][m+1];


        int max=0;
        for(int i=n-1;i>=0;i--){

            for(int j=m-1;j>=0;j--){
                if(x.charAt(i)==y.charAt(j)){
                    mat[i][j]=mat[i+1][j+1]+1;
                    max=Math.max(mat[i][j], max);
                }
            }
        }

        return max;
    }
public static void main(String[] args) throws Exception{
    InputStreamReader ip=new InputStreamReader(System.in);
    BufferedReader br = new BufferedReader(ip);
    int t= Integer.parseInt(br.readLine());
    
    while(t-->0){
    //    int n=Integer.parseInt(br.readLine());//Integer.parseInt(strs[0]);
        // String[] strs=(br.readLine()).trim().split(" ");
        // int n=(int)Long.parseLong(strs[0]),k=(int)Long.parseLong(strs[1]);//,x=Long.parseLong(strs[2]);
        String X=(br.readLine()).trim();
        String Y=(br.readLine()).trim();
        int m = X.length();
        int n = Y.length();
        
        // int max=LCSubStr(X.toCharArray(),Y.toCharArray(), m,n);
        int max=longComSubString(X, Y);
        int ans=(m+n)-2*max;
        System.out.println(ans);

         }
    }
}







//Q2
// public static void main(String[] args) throws Exception{
//     InputStreamReader ip=new InputStreamReader(System.in);
//     BufferedReader br = new BufferedReader(ip);
//     int t= Integer.parseInt(br.readLine());
    
//     while(t-->0){
//        int n=Integer.parseInt(br.readLine());//Integer.parseInt(strs[0]);
//         String[] strs=(br.readLine()).trim().split(" ");
//         int n=(int)Long.parseLong(strs[0]),k=(int)Long.parseLong(strs[1]);//,x=Long.parseLong(strs[2]);
       
//         int st=-1,ed=-1;
//         int idx=0;int ct=0;
//         for(char ch:str.toCharArray()){

//             if(ch=='*' && st==-1){
//                 st=idx; ct++;
//             }else if(ch=='*'){
//                 ed=idx; ct++;
//             }
//             idx++;
//         }


//         if(ct<3){
//             System.out.println(ct);  continue;  //"aa=="+
//         }


//          idx=st;
//         int ans=2;
//         while((idx+k)<ed){
//             if((idx+k)>=ed || (idx+k)>=n)break;

//             int mi=-1;
//             for(int j=idx+1;j<=(idx+k);j++){
//                 if(str.charAt(j)=='*'){
//                     mi=j;
//                 }
//             }

//             if(mi>0){ans++; idx=mi;}
//         }

//         System.out.println(ans);//"aa=="+
//     }
// }
// }






//Q1

// public static void main(String[] args) throws Exception{
//     InputStreamReader ip=new InputStreamReader(System.in);
//     BufferedReader br = new BufferedReader(ip);
//     int t= Integer.parseInt(br.readLine());
    
//     while(t-->0){
//     //    int n=Integer.parseInt(br.readLine());//Integer.parseInt(strs[0]);
//         String[] strs=(br.readLine()).trim().split(" ");
//         long n=Long.parseLong(strs[0]),m=Long.parseLong(strs[1]),x=Long.parseLong(strs[2]);//,k=Integer.parseInt(strs[2]);

//         long row=(x%n);
//         if(row==0){row=(long)n;}
//         long col=(long)Math.ceil((x*1.0)/n);

//         long val=0;

//         // for(int i=1;i<(int)row;i++){
//             val+=m*(row-1);
//         // }

//         val+=col;

//         System.out.println(val);  //"aa="+
//     }
// }

// }