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.util.*;
    import java.io.*;
    import java.math.*;
     
    public class Main {
        static PrintWriter out;
        static Reader in;
        public static void main(String[] args) throws IOException {
            //out = new PrintWriter(new File("out.txt"));
            //PrintWriter out = new PrintWriter(System.out);
            //in = new Reader(new FileInputStream("in.txt"));
            //Reader in = new Reader();
            input_output();
            Main solver = new Main();
            solver.solve();
            out.flush();
            out.close();
     
        }
     
        static long INF = (long)1e16;
        static int maxn = (int)1e6+1000;
        static int mod=(int)1e9+7 ;
        static int n, m, q, k, t;
     

        void solve() throws IOException{
            t = in.nextInt();

            while (t --> 0) {
                String s = in.next(),
                       tt = in.next();

                n = s.length();
                m = tt.length();

                int[][] dp = new int[n+1][m+1];
                boolean ans = false;

                // Dividing the string
                for (int div = 1; div <= m; div++) {

                    for (int i = 0; i <= n; i++)
                        for (int j = 0; j <= m; j++)
                            dp[i][j] = -1;
                    dp[0][0] = 0;

                    for (int i = 0; i < n; i++) { // traversing the string
                        for (int j = 0; j <= i; j++) {
                            if (j == m) break;
                            if (tt.charAt(j) == s.charAt(i) && dp[i][j] != -1) {
                                dp[i+1][j+1] = Math.max(dp[i+1][j+1],dp[i][j]);
                            }
                            if (dp[i][j] != -1 && dp[i][j]+div < m && tt.charAt(dp[i][j]+div) == s.charAt(i)) {
                                dp[i+1][j] = Math.max(dp[i+1][j], dp[i][j]+1);
                            }
                            dp[i+1][j] = Math.max(dp[i+1][j], dp[i][j]);
                            dp[i+1][j+1] = Math.max(dp[i+1][j+1], dp[i][j+1]);
                        }
                    }

                    if (dp[n][div] == m-div) ans = true;
                }

                if (ans) out.println("YES");
                else out.println("NO");
            }
        }
     
        //<>
     
        static class Reader {
     
            private InputStream mIs;
            private byte[] buf = new byte[1024];
            private int curChar;
            private int numChars;
        
            public Reader() {
                this(System.in);
            }
        
            public Reader(InputStream is) {
                mIs = is;
            }
        
            public int read() {
                if (numChars == -1) {
                    throw new InputMismatchException();
        
            }
                if (curChar >= numChars) {
                    curChar = 0;
                    try {
                        numChars = mIs.read(buf);
                    } catch (IOException e) {
                        throw new InputMismatchException();
                    }
                    if (numChars <= 0) {
                        return -1;
                    }
                }
                return buf[curChar++];
            }
        
            public String nextLine() {
                int c = read();
                while (isSpaceChar(c)) {
                    c = read();
                }
                StringBuilder res = new StringBuilder();
                do {
                    res.appendCodePoint(c);
                    c = read();
                } while (!isEndOfLine(c));
                return res.toString();
            }
        
            public String next() {
                int c = read();
                while (isSpaceChar(c)) {
                    c = read();
                }
                StringBuilder res = new StringBuilder();
                do {
                    res.appendCodePoint(c);
                    c = read();
                } while (!isSpaceChar(c));
                return res.toString();
            }
        
            double nextDouble()
            {
                return Double.parseDouble(next());
            }
        
            public long nextLong() {
                int c = read();
                while (isSpaceChar(c)) {
                    c = read();
                }
                int sgn = 1;
                if (c == '-') {
                    sgn = -1;
                    c = read();
                }
                long res = 0;
                do {
                    if (c < '0' || c > '9') {
                        throw new InputMismatchException();
                    }
                    res *= 10;
                    res += c - '0';
                    c = read();
                } while (!isSpaceChar(c));
                return res * sgn;
            }
        
            public int nextInt() {
                int c = read();
                while (isSpaceChar(c)) {
                    c = read();
                }
                int sgn = 1;
                if (c == '-') {
                    sgn = -1;
                    c = read();
                }
                int res = 0;
                do {
                    if (c < '0' || c > '9') {
                        throw new InputMismatchException();
                    }
                    res *= 10;
                    res += c - '0';
                    c = read();
                } while (!isSpaceChar(c));
                return res * sgn;
            }
        
            public boolean isSpaceChar(int c) {
                return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
            }
        
            public boolean isEndOfLine(int c) {
                return c == '\n' || c == '\r' || c == -1;
            }
     
        }
        static void input_output() throws IOException {
            File f = new File("in.txt");
            if(f.exists() && !f.isDirectory()) { 
                in = new Reader(new FileInputStream("in.txt"));
            } else in = new Reader();
            f = new File("out.txt");
            if(f.exists() && !f.isDirectory()) {
                out = new PrintWriter(new File("out.txt"));
            } else out = new PrintWriter(System.out);
        }
    }