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 {
    static int[][] next;
    public static void main(String[] args) {
        FastScanner scanner = new FastScanner();
        PrintWriter out = new PrintWriter(System.out, false);
        int t = scanner.nextInt();
        top:
        while(t-->0) {
            char[] start = scanner.next().toCharArray();
            String target = scanner.next();
            int n = target.length();
            //check ss
            int p = 0;
            boolean good = true;
            for(int i = 0; i < target.length(); i++) {
                char cc = target.charAt(i);
                while(p < start.length && start[p] != cc) p++;
                if (p == start.length) {
                    good = false;
                    break;
                }
                p++;
            }
            if (good) {
                out.println("YES");
                continue;
            }
            next = new int[start.length + 1]['z'+1];
            for(int j = 0; j <= 'z'; j++) {
                next[start.length][j] = start.length;
            }
            for(int i = start.length-1; i >= 0; i--) {
                for(int j = 0; j <= 'z'; j++) {
                    next[i][j] = next[i+1][j];
                    if (start[i] == j) next[i][j] = i;
                }
            }
            for(int i = 1; i < n; i++) {
                if (solve(target.substring(0,i).toCharArray(), target.substring(i, n).toCharArray(), start)) {
                    out.println("YES");
                    continue top;
                }
            }
            out.println("NO");
        }
        out.flush();
    }
    static boolean solve(char[] s1, char[] s2, char[] base) {
        int n = s1.length;
        int m = s2.length;
        int len = base.length;
        int[][] dp = new int[n + 1][m + 1];
        for(int[] dd: dp) Arrays.fill(dd, Integer.MAX_VALUE/3);
        dp[0][0] = 0;
        for(int i = 0; i <= n; i++) {
            for(int j = 0; j<= m; j++) {
                if (dp[i][j] == Integer.MAX_VALUE/3) continue;
                if(i < n && next[dp[i][j]][s1[i]]!=len) {
                    dp[i + 1][j] = Math.min(dp[i+1][j], next[dp[i][j]][s1[i]] + 1);
                }
                if (j < m && next[dp[i][j]][s2[j]]!=len) {
                    dp[i][j+1] = Math.min(dp[i][j+1], next[dp[i][j]][s2[j]] + 1);
                }
            }
        }
        return dp[n][m] != Integer.MAX_VALUE/3;
    }
    public static class FastScanner {
        BufferedReader br;
        StringTokenizer st;
        
        public FastScanner(Reader in) {
            br = new BufferedReader(in);
        }
        
        public FastScanner() {
            this(new InputStreamReader(System.in));
        }
        
        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }
        
        int nextInt() {
            return Integer.parseInt(next());
        }
        
        long nextLong() {
            return Long.parseLong(next());
        }
        
        double nextDouble() {
            return Double.parseDouble(next());
        }
        
        String readNextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }
}
