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.util.stream.Collectors;

/**
 * http://codeforces.com/contest/1506/problem/B
 */
public class C {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int amount = in.nextInt();
        for (int i = 0; i < amount; i++) {
            String string1 = in.next();
            String string2 = in.next();
            System.out.println(solve(string1, string2));
        }
    }

    private static int solve(String string1, String string2) {
        int[] chars1 = new int['z' - 'a' + 1];
        int[] chars2 = new int['z' - 'a' + 1];
        for (int i = 0; i < string1.length(); i++) {
            chars1[string1.charAt(i) - 'a']++;
        }
        for (int i = 0; i < string2.length(); i++) {
            chars2[string2.charAt(i) - 'a']++;
        }
        Set<Character> chars = new HashSet<>();
        for (int i = 0; i < chars1.length; i++) {
            int count = Math.min(chars1[i], chars2[i]);
            if (count > 0) {
                chars.add((char) ('a' + i));
            }
        }
        int lenSum = string1.length() + string2.length();
        if (chars.isEmpty()) {
            return lenSum;
        }
        String regex = "[^" + chars.stream().map(String::valueOf).collect(Collectors.joining()) + "]+";
        List<Set<String>> values = new ArrayList<>();
        String minStr = string1.length() > string2.length() ? string2 : string1;
        String maxStr = string1.length() > string2.length() ? string1 : string2;
        int max = Math.min(string1.length(), string2.length());
        for (int i = 0; i < max; i++) {
            values.add(new HashSet<>());
        }
        Arrays.stream(minStr.split(regex))
                .filter(a -> a.length() > 0)
                .forEach(a -> values.get(a.length() - 1).add(a));
        for (int i = max - 1; i >= 0; i--) {
            for (String value : values.get(i)) {
                if (maxStr.contains(value)) {
                    return lenSum - 2 * value.length();
                }
                values.get(i - 1).add(value.substring(1));
                values.get(i - 1).add(value.substring(0, value.length() - 1));
            }
//            System.out.println(values);
        }
//        System.out.println(values);
        return -1;
    }

}
