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.*;

public class e {
    public static PrintWriter out;
    public static FS sc;
    public static void main(String[] Args) 
        throws Exception
    {
        sc = new FS(System.in);
        out = new PrintWriter(
              new BufferedWriter(
              new OutputStreamWriter(System.out)));

        int t = sc.nextInt();
        while (t-->0) {
            String s = sc.next();
            String a = sc.next();
            out.println((!defNo(s,a) && defYes(s,a)) ? "YES" : "NO");
        }
        
        out.close();
    }
	public static boolean defNo(String s, String a) {
            s = s + s;
            int n = s.length();
            int m = a.length();
            int fptr = 0;
            int i;
            for (i = 0; i < m; i++) {
                while (fptr < n && s.charAt(fptr) != a.charAt(i))
                    fptr++;
                if (fptr == n) break;
                fptr++;
            }
		return i!= m;
		}
	public static int[][] tried = new int[401][401];
	public static int n, m, split;
	public static char[] ss, aa;
	public static boolean defYes(String s, String a) {
		n = s.length();
		m = a.length();
		ss = new char[n];
		aa = new char[m];
		int[] count = new int[26];
		
		for (int i = 0; i < n; i++)
			count[(ss[i] = s.charAt(i))-'a']++;
		for (int i = 0; i < m; i++){
			count[(aa[i] = a.charAt(i))-'a']++;
		}
		for (int i = 0; i < 26; i++)
			if (count[i] < 0)
				return false;
		for (int j = 0; j <= m; j++) {
			split = j;
			for (int[] x : tried)
				Arrays.fill(x, n);
			if (rec(0,split,0))
				return true;
		}
		return false;
	}
	public static boolean rec(int a, int b, int c) {
		if (a == split && b == m)
			return true;
		if (tried[a][b] <= c)
			return false;
		if (a < split && ss[c] == aa[a] && rec(a+1,b,c+1))
			return true;
		if (b < m && ss[c] == aa[b] && rec(a, b+1, c+1))
			return true;
		if ((a < split && ss[c] == aa[a]) || (b < m && ss[c] == aa[b])){
			
		tried[a][b] = c;
			return false;
		}
		if (rec(a,b,c+1))
			return true;
		tried[a][b] = c;
		return false;
	}

    public static int getCurPow(long cap) {
        int curPow = 0;
        while (((1l<<curPow)&cap) == 0)
            curPow++;
        return curPow;
    }

    public static class FS {
        BufferedReader br;
        StringTokenizer st;
        FS(InputStream in) throws Exception {
            br = new BufferedReader(new InputStreamReader(in));
            st = new StringTokenizer(br.readLine());
        }
        String next() throws Exception {
            if (st.hasMoreTokens())
                return st.nextToken();
            st = new StringTokenizer(br.readLine());
            return next();
        }

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

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

        double nextDouble() throws Exception {
            return Double.parseDouble(next());
        }
    }
}
