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.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.nio.file.Paths;
import java.util.*;
public class Main extends PrintWriter {
    static BufferedReader s = new BufferedReader(new InputStreamReader(System.in));Main () { super(System.out); }public static void main(String[] args) throws IOException{ Main  d1=new Main   ();d1.main();d1.flush(); }

    void main() throws IOException {
        StringBuilder sb = new StringBuilder();

        int t = 1;
        t=i(s()[0]);
//        System.out.println(Math.log(10));
        while(t-->0) {
//              String[] s1=s();
            char[] a=s()[0].toCharArray();
            char[] b=s()[0].toCharArray();
            int n = a.length;int m=b.length;
            int ans =0;
            for(int i=0;i<n;i++){
              StringBuilder sb1=new StringBuilder();
              for(int j=i;j<n;j++){
                  sb1.append(a[j]);
                  for(int k=0;k<m;k++){
                      StringBuilder sb2=new StringBuilder();
                      for(int l=k;l<m;l++){
                          sb2.append(b[l]);
                          if(sb1.toString().equals(sb2.toString())){
                              ans=Math.max(ans,sb1.length());
                          }
                      }
                  }
              }
            }sb.append((n-ans)+(m-ans)+"\n");
                    }
        System.out.println(sb);
    }
    static HashMap<Integer,Integer> h;
    static int[] vis;
    static ArrayList<Integer> ans;static long max=0;
    public static void dfs(ArrayList<Integer> [] adj,int i){
        vis[i] =1 ;
        if(adj[i]==null) return;
        int flag = 0;
         long sum = 0;
        for(int j:adj[i]){
            if(vis[j] ==1){
                sum+=adj[j].size();
//                System.out.println(i+" "+j);
            }else {
                sum+=adj[j].size();
                dfs(adj,j);
            }
        }
        if(sum>max){
            max=sum;
            ans=new ArrayList<>();
            ans.add(i);
        }else if(sum==max){
            ans.add(i);
        }
    }
    //        System.out.println(sb);
    static long gcd(long a, long b) {
        if (b == 0)
            return a;
        return gcd(b, a % b);
    }
    static String[] s() throws IOException { return s.readLine().trim().split("\\s+"); }
    static int i(String ss) {return Integer.parseInt(ss); }
    static long l(String ss) {return Long.parseLong(ss); }
    public void arr(long[] a,int n) throws IOException {String[] s2=s();for(int i=0;i<n;i++){ a[i]=l(s2[i]); }}
    public void arri(int[] a,int n) throws IOException {String[] s2=s();for(int i=0;i<n;i++){ a[i]=i(s2[i]); }}
}class Pair{
    int prio,ind;
    public Pair(int a,int b){
        this.prio=a;this.ind=b;
    }
}


