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.*;
import java.nio.Buffer;
import java.util.*;

public class Main {
    static Reader br = new Reader();
    static int mod = 1000000007;

    public static long gcd(long a, long b) {
        while (b > 0) {
            long c = a;
            a = b;
            b = c % b;
        }
        return a;
    }

    public static int ni() throws IOException {
        return br.nextInt();
    }

    public static int max(int a, int b) {
        return Integer.max(a, b);
    }

    public static long max(long a, long b) {
        return Long.max(a, b);
    }

    public static double max(double a, double b) {
        return Double.max(a, b);
    }

    public static int min(int a, int b) {
        return Integer.min(a, b);
    }

    public static long min(long a, long b) {
        return Long.min(a, b);
    }

    public static double min(double a, double b) {
        return Double.min(a, b);
    }


    public static long nl() throws IOException {
        return br.nextLong();
    }

    public static double nd() throws IOException {
        return br.nextDouble();
    }

    public static int[] nia(int n) throws IOException {
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = ni();
        }
        return a;
    }

    public static long[] nil(int n) throws IOException {
        long[] a = new long[n];
        for (int i = 0; i < n; i++) {
            a[i] = nl();
        }
        return a;
    }

    static boolean isPowerOfTwo(long x) {
      /* First x in the below expression is
        for the case when x is 0 */
        return x != 0 && ((x & (x - 1)) == 0);

    }

    static boolean isPrime(int n) {
        // Corner case
        if (n <= 1)
            return false;

        // Check from 2 to n-1
        for (int i = 2; i < n; i++)
            if (n % i == 0)
                return false;

        return true;
    }

    public static long log(long x, int b) {
        return (long) (Math.log(x) / Math.log(b));
    }

    static int countDigits(long l) {
        if (l >= 1000000000000000000L) return 19;
        if (l >= 100000000000000000L) return 18;
        if (l >= 10000000000000000L) return 17;
        if (l >= 1000000000000000L) return 16;
        if (l >= 100000000000000L) return 15;
        if (l >= 10000000000000L) return 14;
        if (l >= 1000000000000L) return 13;
        if (l >= 100000000000L) return 12;
        if (l >= 10000000000L) return 11;
        if (l >= 1000000000L) return 10;
        if (l >= 100000000L) return 9;
        if (l >= 10000000L) return 8;
        if (l >= 1000000L) return 7;
        if (l >= 100000L) return 6;
        if (l >= 10000L) return 5;
        if (l >= 1000L) return 4;
        if (l >= 100L) return 3;
        if (l >= 10L) return 2;
        return 1;
    }

    public static void main(String[] args) throws IOException {
        //a();
        //b();
        c();
        //d();
        //e();
    }

    //Problem A
    static void a() throws IOException {
        int t = ni();
        while (t-- > 0) {
            int n = ni();
            int m = ni();
            long x = nl();

            long i = x / n;
            long j;
            if (n * i != x) {
                j = x - n * i;
                i = i + 1;
            } else
                j = n;


            long ans = (j - 1) * m;
            ans += i;

            System.out.println(ans);

        }
    }

    //Problem B
    static void b() throws IOException {
        BufferedReader bx = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(bx.readLine());
        while (t-- > 0) {
            String[] in = bx.readLine().split(" ");
            int n = Integer.parseInt(in[0]);
            int k = Integer.parseInt(in[1]);
            String[] input = bx.readLine().split("");
            int[] list = new int[n];
            int count = 0;
            int star_count = 0;
            int flag = 0;
            for (int i = 0; i < n; i++) {
                if (input[i].equals("*")) {
                    star_count++;
                    if (flag == 0) {
                        list[i] = 2;//x
                        count++;
                        flag = 1;
                    } else
                        list[i] = 1;//*
                } else
                    list[i] = 0;//.

            }
            if (star_count > 1)
                for (int i = n - 1; i > 0; i--) {
                    if (list[i] == 1) {
                        list[i] = 2;
                        count++;
                        break;
                    }
                }

            if (star_count > 2) {
                for (int i = 0; i < n; i++) {
                    if (list[i] == 2) {
                        for (int j = i + 1; j <= min(k + i, n - 1); j++) {
                            if (list[j] == 2) {
                                i = j - 1;
                                break;
                            }
                        }
                        int j = min(k + i, n - 1);
                        for (; j > i; j--) {
                            if (list[j] == 1) {
                                list[j] = 2;
                                count++;
                                i = j - 1;
                                break;
                            }
                        }

                    }
                }
            }
            System.out.println(count);


        }
    }

    //Problem C
    static void c() throws IOException {
        BufferedReader bx = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(bx.readLine());
        while (t-- > 0) {
            String a = bx.readLine();
            int la = a.length();
            String b = bx.readLine();
            int lb = b.length();
            int max_length=0;
            int[][] dp = new int[la][lb];

            for (int i = 0; i < la; i++) {
                for (int j = 0; j < lb; j++) {
                    if(a.charAt(i) == b.charAt(j)){
                        if(i==0 || j==0)
                            dp[i][j] = 1;
                        else
                            dp[i][j] = dp[i-1][j-1]+1;
                    }
                    max_length = max(max_length,dp[i][j]);
                }
            }

            System.out.println(la-max_length + lb-max_length);
        }
    }

    //Problem D
    static void d() throws IOException {
        int t = ni();
        while (t-- > 0) {
            //int n = ni();
        }
    }

    //Problem E
    static void e() throws IOException {
        int t = ni();
        while (t-- > 0) {
            //int n = ni();
        }
    }


    static class Reader {
        final private int BUFFER_SIZE = 1 << 16;
        private DataInputStream din;
        private byte[] buffer;
        private int bufferPointer, bytesRead;

        public Reader() {
            din = new DataInputStream(System.in);
            buffer = new byte[BUFFER_SIZE];
            bufferPointer = bytesRead = 0;
        }

        public Reader(String file_name) throws IOException {
            din = new DataInputStream(new FileInputStream(file_name));
            buffer = new byte[BUFFER_SIZE];
            bufferPointer = bytesRead = 0;
        }

        public String readLine() throws IOException {
            byte[] buf = new byte[64]; // line length
            int cnt = 0, c;
            while ((c = read()) != -1) {
                if (c == '\n')
                    break;
                buf[cnt++] = (byte) c;
            }
            return new String(buf, 0, cnt);
        }

        public int nextInt() throws IOException {
            int ret = 0;
            byte c = read();
            while (c <= ' ')
                c = read();
            boolean neg = (c == '-');
            if (neg)
                c = read();
            do {
                ret = ret * 10 + c - '0';
            } while ((c = read()) >= '0' && c <= '9');

            if (neg)
                return -ret;
            return ret;
        }

        public long nextLong() throws IOException {
            long ret = 0;
            byte c = read();
            while (c <= ' ')
                c = read();
            boolean neg = (c == '-');
            if (neg)
                c = read();
            do {
                ret = ret * 10 + c - '0';
            }
            while ((c = read()) >= '0' && c <= '9');
            if (neg)
                return -ret;
            return ret;
        }

        public double nextDouble() throws IOException {
            double ret = 0, div = 1;
            byte c = read();
            while (c <= ' ')
                c = read();
            boolean neg = (c == '-');
            if (neg)
                c = read();

            do {
                ret = ret * 10 + c - '0';
            }
            while ((c = read()) >= '0' && c <= '9');

            if (c == '.') {
                while ((c = read()) >= '0' && c <= '9') {
                    ret += (c - '0') / (div *= 10);
                }
            }

            if (neg)
                return -ret;
            return ret;
        }

        private void fillBuffer() throws IOException {
            bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);
            if (bytesRead == -1)
                buffer[0] = -1;
        }

        private byte read() throws IOException {
            if (bufferPointer == bytesRead)
                fillBuffer();
            return buffer[bufferPointer++];
        }

        public void close() throws IOException {
            if (din == null)
                return;
            din.close();
        }
    }
}
