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.util.Arrays;
import java.util.StringTokenizer;


public class Main {
    static PrintWriter pw;
    static MScanner sc;

    public static void main(String[] args) throws Exception {
        sc = new MScanner(System.in);
        pw = new PrintWriter(System.out);
        solve();
        pw.flush();
    }

    private static void solve() throws IOException {
        int t = sc.nextInt();
        while (t-- > 0) {
            char[] a = sc.nextLine().toCharArray();
            char[] b = sc.nextLine().toCharArray();

            int result = a.length + b.length;

            for (int ai = 0; ai < a.length; ++ai) {
                for (int aj = ai; aj < a.length; ++aj) {
                    int len = aj - ai + 1;
                    int lenMinusOne = len - 1;
                    for (int bi = 0; bi + lenMinusOne < b.length; ++bi) {
                        boolean equal = true;
                        for (int check = 0; check < len; ++check) {
                            if (a[ai + check] != b[bi + check]) {
                                equal = false;
                                break;
                            }
                        }
                        int candidate = a.length + b.length - 2 * len;
                        if (equal && result > candidate) {
                            result = candidate;
                        }
                    }
                }
            }

            pw.println(result);
        }
    }

    static void shuffle(int[] in) {
        for (int i = 0; i < in.length; i++) {
            int idx = (int) (Math.random() * in.length);
            int tmp = in[i];
            in[i] = in[idx];
            in[idx] = tmp;
        }
    }

    static void shuffle(long[] in) {
        for (int i = 0; i < in.length; i++) {
            int idx = (int) (Math.random() * in.length);
            long tmp = in[i];
            in[i] = in[idx];
            in[idx] = tmp;
        }
    }

    static class MScanner {
        StringTokenizer st;
        BufferedReader br;

        public MScanner(InputStream system) {
            br = new BufferedReader(new InputStreamReader(system));
        }

        public MScanner(String file) throws Exception {
            br = new BufferedReader(new FileReader(file));
        }

        public String next() throws IOException {
            while (st == null || !st.hasMoreTokens())
                st = new StringTokenizer(br.readLine());
            return st.nextToken();
        }

        public int[] intArr(int n) throws IOException {
            int[] in = new int[n];
            for (int i = 0; i < n; i++) in[i] = nextInt();
            return in;
        }

        public long[] longArr(int n) throws IOException {
            long[] in = new long[n];
            for (int i = 0; i < n; i++) in[i] = nextLong();
            return in;
        }

        public int[] intSortedArr(int n) throws IOException {
            int[] in = new int[n];
            for (int i = 0; i < n; i++) in[i] = nextInt();
            shuffle(in);
            Arrays.sort(in);
            return in;
        }

        public long[] longSortedArr(int n) throws IOException {
            long[] in = new long[n];
            for (int i = 0; i < n; i++) in[i] = nextLong();
            shuffle(in);
            Arrays.sort(in);
            return in;
        }

        public Integer[] IntegerArr(int n) throws IOException {
            Integer[] in = new Integer[n];
            for (int i = 0; i < n; i++) in[i] = nextInt();
            return in;
        }

        public Long[] LongArr(int n) throws IOException {
            Long[] in = new Long[n];
            for (int i = 0; i < n; i++) in[i] = nextLong();
            return in;
        }

        public String nextLine() throws IOException {
            return br.readLine();
        }

        public int nextInt() throws IOException {
            return Integer.parseInt(next());
        }

        public double nextDouble() throws IOException {
            return Double.parseDouble(next());
        }

        public char nextChar() throws IOException {
            return next().charAt(0);
        }

        public long nextLong() throws IOException {
            return Long.parseLong(next());
        }

        public boolean ready() throws IOException {
            return br.ready();
        }
    }
}

//
//class Pair implements Comparable<Pair> {
//    public int x;
//    public int y;
//
//    public Pair(int x, int y) {
//        this.x = x;
//        this.y = y;
//    }
//
//    @Override
//    public String toString() {
//        return (x + " " + y);
//    }
//
//    @Override
//    public boolean equals(Object o) {
//        if (!(o instanceof Pair)) return false;
//        Pair pairo = (Pair) o;
//        return this.x == pairo.x &&
//                this.y == pairo.y;
//    }
//
//    @Override
//    public int compareTo(Pair p) {
//        return Integer.compare(this.x, p.x);
//    }
//}
//
//class Maths {
//    public final long MOD = (long) 1e9 + 7;
//    public long[] fact = generateFactorials(1000000);
//    public long[] invFact = generateReverseFactorials(1000000);
//
//    public static long modInverse(long a, long m) {
//        return power(a, m - 2, m);
//    }
//
//    public static long gcd(long a, long b) {
//        if (a == 0)
//            return b;
//        return gcd(b % a, a);
//    }
//
//    public static long power(long a, long k, long m) {
//        long res = 1;
//        while (k > 0) {
//            if ((k & 1) != 0) {
//                res = res * a % m;
//            }
//            a = a * a % m;
//            k >>= 1;
//        }
//        return res;
//    }
//
//    public long comb(final int m, final int n) {
//        return (((fact[n] * invFact[m]) % MOD) * invFact[n - m]) % MOD;
//    }
//
//    public long[] generateFactorials(int count) {
//        long[] result = new long[count];
//        result[0] = 1;
//        for (int i = 1; i < count; i++) {
//            result[i] = (result[i - 1] * i) % MOD;
//        }
//        return result;
//    }
//
//    long[] generateReverseFactorials(int upTo) {
//        final long[] reverseFactorials = new long[upTo];
//        reverseFactorials[0] = reverseFactorials[1] = 1;
//        final BigInteger BIG_MOD = BigInteger.valueOf(MOD);
//        for (int i = 1; i < upTo; i++) {
//            reverseFactorials[i] = (BigInteger.valueOf(i).modInverse(BIG_MOD).longValue() * reverseFactorials[i - 1]) % MOD;
//        }
//        return reverseFactorials;
//    }
//}
//
//class Node {
//    List<Integer> neighbors;
//
//    Node() {
//        neighbors = new ArrayList<>();
//    }
//
//    void addEdge(Integer v) {
//        neighbors.add(v);
//    }
//
//    public List<Integer> getNeighbors() {
//        return neighbors;
//    }
//}
//
//class Graph {
//    List<Node> nodes = new ArrayList<>();
//
//    public Graph(int n) {
//        for (int i = 0; i < n; ++i) {
//            nodes.add(new Node());
//        }
//    }
//
//    public Node getNode(int v) {
//        return nodes.get(v);
//    }
//
//    public void addEdge(int u, int v) {
//        getNode(u).addEdge(v);
//        getNode(v).addEdge(u);
//    }
//}