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 {
    public static void main(String[] args) throws IOException {
        PrintWriter out = new PrintWriter(System.out);
        //Scanner sc = new Scanner();
        Reader in = new Reader();
        Main solver = new Main();
        solver.solve(out, in);
        out.flush();
        out.close();
 
    }
 
    static int INF = (int)1e9;
    static int maxn = 2*(int)1e5+5;
    static int mod= 1000000321 ;
    static int n,m,k,t,q,d,p;
    
    static ArrayList<Integer> adj[];
    
    void solve(PrintWriter out, Reader in) throws IOException{
        t = in.nextInt();
        
        while (t-->0) {
            String s = in.next();
            String d = in.next();
            n = s.length();
            m = d.length();
            int z = 0;
            boolean flag = false;
            
            for (int b = 0; b < m-1; b++) {
                int[][] dp = new int[n][b+2];
                for (int i = 0; i < n; i++)
                    for (int j = 0; j < b+2; j++) 
                        dp[i][j] = -1;
                
                if (s.charAt(0) == d.charAt(0)) {
                    dp[0][1] = 0;
                }
                if (s.charAt(0) == d.charAt(b+1)) {
                    dp[0][0] = 1;
                }
                
                for (int i = 1; i < n; i++) {
                    for (int j = 0; j <= b+1; j++) {
                        if (dp[i-1][j] != -1) {
                            z = dp[i-1][j];
                            if (j != b+1 && s.charAt(i) == d.charAt(j)) {
                                dp[i][j+1] = Math.max(dp[i][j+1], z);
                            }
                            if (z != m-b-1 && s.charAt(i) == d.charAt(b+1+z)) {
                                dp[i][j]   = Math.max(dp[i][j], z+1);
                            }
                        }
                    }
                    if (s.charAt(i) == d.charAt(0)) dp[i][1] = Math.max(dp[i][1], 0);
                    if (s.charAt(i) == d.charAt(b+1)) dp[i][0] = Math.max(dp[i][0], 1);
                    for (int j = 0; j <= b+1; j++) dp[i][j] = Math.max(dp[i-1][j],dp[i][j]);
                }
                
                if (dp[n-1][b+1] == m-b-1) {
                    out.println("YES");
                    flag = true;
                    break;
                }
            }
            
            if (!flag) {
                int cnt = 0;
                for (int i = 0; i < n; i++) {
                    if (cnt == m) break;
                    if (s.charAt(i) == d.charAt(cnt)) cnt++;
                }
                if (cnt == m) 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;
    }
 
    }
}