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

/*
Прокрастинирую
*/

public class Main {

    static FastReader in;
    static PrintWriter out;
    static Random rand = new Random();
    static final int INF = (int) (1e9 + 10);
    static final int MOD = (int) (1e9 + 7);
    static final int N = (int) (1e6);
    static final int LOGN = 60;

    static void solve() {
        char[] s = in.next().toCharArray();
        char[] t = in.next().toCharArray();
        int n = s.length;
        int m = t.length;

        int[][] next = new int[n + 1][26];
        for (int i = n; i >= 1; i--) {
            for (int j = 0; j < 26; j++) {
                next[i][j] = (i == n) ? INF : next[i + 1][j];
            }
            next[i][s[i - 1] - 'a'] = i;
        }

        for (int k = 0; k < m; k++) {
            char[] a = Arrays.copyOfRange(t, 0, k);
            char[] b = Arrays.copyOfRange(t, k, m);
            int n1 = a.length;
            int n2 = b.length;

            int[][] dp = new int[n1 + 1][n2 + 1];

            for (int i = 0; i <= n1; i++) {
                for (int j = 0; j <= n2; j++) {
                    if (i == 0 && j == 0) continue;
                    dp[i][j] = INF;
                    if (i > 0 && dp[i - 1][j] < n) {
                        dp[i][j] = Math.min(dp[i][j], next[dp[i - 1][j] + 1][a[i - 1] - 'a']);
                    }
                    if (j > 0 && dp[i][j - 1] < n) {
                        dp[i][j] = Math.min(dp[i][j], next[dp[i][j - 1] + 1][b[j - 1] - 'a']);
                    }
                }
            }

            if (dp[n1][n2] <= n) {
                out.println("YES");
                return;
            }
        }

        out.println("NO");
    }

    public static void main(String[] args) throws FileNotFoundException {
        in = new FastReader(System.in);
//        in = new FastReader(new FileInputStream("input.txt"));
        out = new PrintWriter(System.out);
//        out = new PrintWriter(new FileOutputStream("output.txt"));


        int q = in.nextInt();

        while (q-- > 0) {
            solve();
        }

        out.close();
    }

    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        FastReader(InputStream is) {
            br = new BufferedReader(new InputStreamReader(is));
        }

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

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

        Double nextDouble() {
            return Double.parseDouble(next());
        }

        String next() {
            while (st == null || !st.hasMoreTokens()) {
                st = new StringTokenizer(nextLine());
            }
            return st.nextToken();
        }

        String nextLine() {
            String s = "";
            try {
                s = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return s;
        }
    }
}