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.math.BigInteger;
import java.util.*;

public class Main  {
    public static void main(String[] args) throws IOException {
        new CC().run();
    }
}
class CC {
    public void run() throws IOException {
        Input in = new Input();
        Output out = new Output();
        int T = in.nextInt();
        for(int t = 0; t < T; t++) {
            String a = in.nextLine();
            String b = in.nextLine();
            int max = 0;
            for(int i = 0; i <= a.length(); i++) {
                for(int j = i + 1; j <= a.length(); j++) {
                    if(b.contains(a.substring(i, j))) {
                        max = Math.max(max, j - i);
                    }
                }
            }
            int ans = a.length() - max + b.length() - max;
            out.println(ans);
        }
        out.flush();
    }
}
class CA {
    public void run() throws IOException {
        Input in = new Input();
        Output out = new Output();
        int T = in.nextInt();
        for(int t = 0; t < T; t++) {
            long n = in.nextLong(), m = in.nextLong(), x = in.nextLong();
            long c = (x-1) / n;
            long r = (x-1) % n;
            long ans = r * m + c + 1;
            out.println(ans);
        }
        out.flush();
    }
}
class B {
    long mod = 1000000007;
    public void run() throws IOException {
        Input in = new Input();
        long N = in.nextLong();
        long n = N / 10;
        long s = sim(N, n);
        System.out.println(s);
    }
    long m(long num) {
        long tmp = num % mod;
        if(tmp < 0) tmp += mod;
        return tmp;
    }
    long sim(long N, long n) {
        long[][] matrix = {
                { 16, 1, 0, 0, 0 },
                {  9, 0, 1, 0, 0 },
                {  4, 0, 0, 1, 0 },
                {  1, 0, 0, 0, 1 },
                {  0, 0, 0, 0, 0 }
        };
        long[][] s = pow(matrix, n);
        long res = 0;
        for(int i = 0; i < 4; i++) {
            res = m(res + s[0][i]);
        }
        if(N % 10 < 5) {
            res = m(res + s[0][4]);
        }
        return res;
    }
    long[][] mul(long[][] m1, long[][] m2) {
        int len = m1.length;
        long[][] res = new long[len][len];
        for(int r = 0; r < len; r++) {
            for(int c = 0; c < len; c++) {
                for(int k = 0; k < len; k++) {
                    long prod = m(m1[r][k] * m2[k][c]);
                    res[r][c] = m(res[r][c] + prod);
                }
            }
        }
        return res;
    }
    long[][] pow(long[][] m, long pow) {
        int len = m.length;
        if(pow == 0) {
            long[][] I = new long[len][len];
            for(int i = 0; i < len; i++) {
                I[i][i] = 1;
            }
            return I;
        }
        long[][] half = pow(m, pow / 2);
        if(pow % 2 == 1) {
            return mul(mul(half, half), m);
        } else {
            return mul(half, half);
        }
    }
}
class C {
    public void run() throws IOException {
        Input in = new Input();

        int a = in.nextInt();
        String s = in.nextLine();

        int[] scan = new int[s.length() + 1];
        int[] sumFreq = new int[9 * s.length() + 1];
        int totalFreqs = 0;
        for(int i = 1; i < scan.length; i++) {
            scan[i] = s.charAt(i - 1) + scan[i - 1] - '0';
            for(int j = 0; j < i; j++) {
                int subseqSum = scan[i] - scan[j];
                sumFreq[subseqSum]++;
                totalFreqs++;
            }
        }

        long ans = 0;
        for(int i = 1; i < scan.length; i++) {
            for(int j = i; j < scan.length; j++) {
                int subseqSum = scan[j] - scan[i - 1];
                if(subseqSum == 0 && a == 0) {
                    ans += totalFreqs;
                } else if (subseqSum > 0 && a % subseqSum == 0) {
                    int factor = a / subseqSum;
                    if(factor < sumFreq.length) {
                        ans += sumFreq[factor];
                    }
                }
            }
        }
        System.out.println(ans);
    }
}
class A {
    public void run() throws IOException {
        Input in = new Input();
        Output out = new Output();

        BigInteger p = BigInteger.valueOf(7901);
        FactPrecomp f = new FactPrecomp(1000, 7901);
        int T = in.nextInt();
        for(int t = 0; t < T; t++) {
            int n = in.nextInt();
            int[] freq = new int[1000];
            for(int i = 0; i < n; i++) {
                int cur = in.nextInt();
                freq[cur - 1]++;
            }
            BigInteger res = BigInteger.ONE;
            for(int i : freq) {
                res = res.multiply(f.fact(i)).mod(p);
            }
            out.println(res.toString());
        }

        out.flush();
    }
}
class FactPrecomp {
    BigInteger[] facts;
    public FactPrecomp(int n, long modulo) {
        BigInteger p = BigInteger.valueOf(modulo);
        facts = new BigInteger[n + 1];
        facts[0] = BigInteger.ONE;
        for(int i = 1; i <= n; i++) {
            facts[i] = facts[i - 1].multiply(BigInteger.valueOf(i).mod(p));
        }
    }
    public BigInteger fact(int k) {
        return facts[k];
    }
}
class Util {
    public static BigInteger fact(int n, BigInteger p) {
        BigInteger res = BigInteger.ONE;
        for(int i = 2; i <= n; i++) {
            res = res.multiply(BigInteger.valueOf(i)).mod(p);
        }
        return res.mod(p);
    }
    public static BigInteger binom(int n, int k, BigInteger p) {
        BigInteger num = fact(n, p);
        BigInteger denom = fact(k, p).multiply(fact(n - k, p)).modInverse(p);
        return num.multiply(denom).mod(p);
    }
}
class Input {
    InputStreamReader r;
    BufferedReader br;
    StringTokenizer st;
    public Input() throws IOException{
        r = new InputStreamReader(System.in);
        br = new BufferedReader(r);
        st = new StringTokenizer(br.readLine());
    }
    public Input(InputStream i) throws IOException{
        r = new InputStreamReader(i);
        br = new BufferedReader(r);
        st = new StringTokenizer(br.readLine());
    }
    public String nextToken() throws IOException{
        if(st.hasMoreTokens()){
            return st.nextToken();
        }
        st = new StringTokenizer(br.readLine());
        return st.nextToken();
    }
    public String nextToken(String delim) throws IOException{
        if(st.hasMoreTokens()){
            return st.nextToken(delim);
        }
        st = new StringTokenizer(br.readLine());
        return st.nextToken(delim);
    }
    public String nextLine() throws IOException{
        if(st.hasMoreTokens()){
            return st.nextToken("\n");
        }
        st = new StringTokenizer(br.readLine());
        return st.nextToken("\n");
    }
    public int nextInt() throws IOException{
        return Integer.parseInt(nextToken());
    }
    public long nextLong() throws IOException{
        return Long.parseLong(nextToken());
    }
    public double nextDouble() throws IOException {
        return Double.parseDouble(nextToken());
    }
    public String[] nextLineSplit(String s) throws IOException{
        return nextLine().split(s);
    }
    public boolean hasMoreTokens(){
        return st.hasMoreTokens();
    }
}
class Output {
    OutputStream out;
    public Output(){
        out = new BufferedOutputStream(System.out);
    }
    public Output(PrintStream o){
        out = new BufferedOutputStream(o);
    }
    public void print(String s) throws IOException{
        out.write(s.getBytes());
    }
    public void print(int i) throws IOException{
        print(i + "");
    }
    public void println(String s) throws IOException{
        out.write((s + "\n").getBytes());
    }
    public void println(int i) throws IOException{
        println(i + "");
    }
    public void println(long i) throws IOException{
        println(i + "");
    }
    public void flush() throws IOException{
        out.flush();
    }
}