You are given a string s. You can build new string p from s using the following operation no more than two times: 

  1. choose any subsequence s_{i_1}, s_{i_2}, ..., s_{i_k} where 1 ≤ i_1 < i_2 < ... < i_k ≤ |s|; 
  2. erase the chosen subsequence from s (s can become empty); 
  3. concatenate chosen subsequence to the right of the string p (in other words, p = p + s_{i_1}s_{i_2}... s_{i_k}). 



Of course, initially the string p is empty. 

For example, let s = ababcd. At first, let's choose subsequence s_1 s_4 s_5 = abc — we will get s = bad and p = abc. At second, let's choose s_1 s_2 = ba — we will get s = d and p = abcba. So we can build abcba from ababcd.

Can you build a given string t using the algorithm above?

Input

The first line contains the single integer T (1 ≤ T ≤ 100) — the number of test cases.

Next 2T lines contain test cases — two per test case. The first line contains string s consisting of lowercase Latin letters (1 ≤ |s| ≤ 400) — the initial string.

The second line contains string t consisting of lowercase Latin letters (1 ≤ |t| ≤ |s|) — the string you'd like to build.

It's guaranteed that the total length of strings s doesn't exceed 400.

Output

Print T answers — one per test case. Print YES (case insensitive) if it's possible to build t and NO (case insensitive) otherwise.

Example

Input


4
ababcd
abcba
a
b
defi
fed
xyz
x


Output


YES
NO
NO
YES
import java.io.*;
import java.util.Arrays;
import java.util.StringJoiner;
import java.util.StringTokenizer;
import java.util.function.Function;

public class MainE {

    public static void main(String[] args) {
        FastScanner sc = new FastScanner(System.in);
        PrintWriter pw = new PrintWriter(System.out);
        int T = sc.nextInt();
        while( T-->0 ) {
            pw.println(solve(sc.next(), sc.next()));
        }
        pw.flush();
    }

    static int INF = 1_000_000;

    static String solve(String S, String T) {

        int[][] NEXT = new int[S.length()+1][];
        int[] last = new int[26];
        Arrays.fill(last, INF);
        NEXT[S.length()] = last;
        for (int i = S.length()-1; i >= 0; i--) {
            int c = S.charAt(i)-'a';
            int[] curr = Arrays.copyOf(NEXT[i+1], 26);
            curr[c] = i;
            NEXT[i] = curr;
        }

        for (int a = 0; a < T.length(); a++) {
            if( isOk(NEXT, T, a) ) {
                return "YES";
            }
        }
        return "NO";
    }

    static boolean isOk(int[][] SNEXT, String T, int A) {
        int TN = T.length();
        int B = TN-A;

        // aとbをつくったときSのどこまで読んだか
        int[][] dp = new int[A+1][B+1];
        for (int[] each : dp) Arrays.fill(each, INF);
        dp[0][0] = 0;
        for (int a = 0; a <= A; a++) {
            for (int b = 0; b <= B; b++) {
                int i = dp[a][b];
                if( i == INF ) continue;

                if( a < A ) {
                    int c = T.charAt(a)-'a';
                    int next = SNEXT[i][c];
                    if( next != INF ) {
                        dp[a+1][b] = Math.min(dp[a+1][b], next+1);
                    }
                }
                if( b < B ) {
                    int c = T.charAt(A+b)-'a';
                    int next = SNEXT[i][c];
                    if( next != INF ) {
                        dp[a][b+1] = Math.min(dp[a][b+1], next+1);
                    }
                }
            }
        }
        return dp[A][B] < INF;
    }

    @SuppressWarnings("unused")
    static class FastScanner {
        private BufferedReader reader;
        private StringTokenizer tokenizer;

        FastScanner(InputStream in) {
            reader = new BufferedReader(new InputStreamReader(in));
            tokenizer = null;
        }

        String next() {
            if (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        String nextLine() {
            if (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    return reader.readLine();
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken("\n");
        }

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

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

        int[] nextIntArray(int n) {
            int[] a = new int[n];
            for (int i = 0; i < n; i++)
                a[i] = nextInt();
            return a;
        }

        int[] nextIntArray(int n, int delta) {
            int[] a = new int[n];
            for (int i = 0; i < n; i++)
                a[i] = nextInt() + delta;
            return a;
        }

        long[] nextLongArray(int n) {
            long[] a = new long[n];
            for (int i = 0; i < n; i++)
                a[i] = nextLong();
            return a;
        }
    }

    static <A> void writeLines(A[] as, Function<A, String> f) {
        PrintWriter pw = new PrintWriter(System.out);
        for (A a : as) {
            pw.println(f.apply(a));
        }
        pw.flush();
    }

    static void writeLines(int[] as) {
        PrintWriter pw = new PrintWriter(System.out);
        for (int a : as) pw.println(a);
        pw.flush();
    }

    static void writeLines(long[] as) {
        PrintWriter pw = new PrintWriter(System.out);
        for (long a : as) pw.println(a);
        pw.flush();
    }

    static int max(int... as) {
        int max = Integer.MIN_VALUE;
        for (int a : as) max = Math.max(a, max);
        return max;
    }

    static int min(int... as) {
        int min = Integer.MAX_VALUE;
        for (int a : as) min = Math.min(a, min);
        return min;
    }

    static void debug(Object... args) {
        StringJoiner j = new StringJoiner(" ");
        for (Object arg : args) {
            if (arg instanceof int[]) j.add(Arrays.toString((int[]) arg));
            else if (arg instanceof long[]) j.add(Arrays.toString((long[]) arg));
            else if (arg instanceof double[]) j.add(Arrays.toString((double[]) arg));
            else if (arg instanceof Object[]) j.add(Arrays.toString((Object[]) arg));
            else j.add(arg.toString());
        }
        System.err.println(j.toString());
    }
}
