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.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.StringTokenizer;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author htvu
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        EEraseSubsequences solver = new EEraseSubsequences();
        solver.solve(1, in, out);
        out.close();
    }

    static class EEraseSubsequences {
        public void solve(int testNumber, InputReader in, PrintWriter out) {
            int INF = (int) 1e9;

            for (int test = in.nextInt(); test > 0; --test) {
                String s = in.next(), p = in.next();
                int[][] next = new int[s.length() + 1][128];
                Arrays.fill(next[s.length()], INF);
                for (int i = s.length() - 1; i >= 0; --i) {
                    System.arraycopy(next[i + 1], 'a', next[i], 'a', 26);
                    next[i][s.charAt(i)] = i;
                }
//            for (int i=0;i<s.length();++i) {
//                for (int c='a';c<='z';++c)
//                    if (next[i][c] > -1)
//                        out.print((char)c + ":" + next[i][c] + " " );
//                out.println();
//            }

                int[][] dp = new int[s.length() + 1][s.length() + 1];
                boolean found = false;
                for (int si = 1; si <= p.length(); ++si) {
                    String a = p.substring(0, si), b = p.substring(si);
                    int m = a.length(), n = b.length();
                    for (int i = 0; i <= m; ++i)
                        Arrays.fill(dp[i], INF);
                    dp[0][0] = 0;

                    for (int i = 0; i <= m; ++i)
                        for (int j = 0; j <= n; ++j)
                            if (dp[i][j] < INF) {
                                int len = dp[i][j];
                                if (i < m) {
                                    int nexta = next[len][a.charAt(i)];
                                    dp[i + 1][j] = Math.min(dp[i + 1][j], nexta + 1);
                                }

                                if (j < n) {
                                    int nextb = next[len][b.charAt(j)];
                                    dp[i][j + 1] = Math.min(dp[i][j + 1], nextb + 1);
                                }
                            }
                    if (dp[m][n] < INF) {
                        found = true;
                        break;
                    }
                }
                out.println(found ? "YES" : "NO");
            }
        }

    }

    static class InputReader {
        public BufferedReader reader;
        public StringTokenizer tokenizer;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }

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

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

    }
}

