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
/*
If you want to aim high, aim high
Don't let that studying and grades consume you
Just live life young
******************************
If I'm the sun, you're the moon
Because when I go up, you go down
*******************************
I'm working for the day I will surpass you
https://www.a2oj.com/Ladder16.html
*/
import java.util.*;
import java.io.*;
import java.math.*;

   public class x1303E
   {
      public static void main(String omkar[]) throws Exception
      {
         BufferedReader infile = new BufferedReader(new InputStreamReader(System.in));  
         StringTokenizer st = new StringTokenizer(infile.readLine());
         int T = Integer.parseInt(st.nextToken());
         while(T-->0)
         {
            String input = infile.readLine();
            String target = infile.readLine();
            if(target.length() > input.length())
            {
               System.out.println("NO");
               continue;
            }
            boolean works = false;
            int N = target.length();
            int M = input.length();
            char[] arr = input.toCharArray();
            //bin searches on input
            TreeSet<Integer>[] bst = new TreeSet[26];
            for(int i=0; i < 26; i++)
               bst[i] = new TreeSet<Integer>();
            for(int i=0; i < M; i++)
               bst[arr[i]-'a'].add(i);
            for(int b=1; b < N; b++)
            {
               String left = target.substring(0, b);
               String right = target.substring(b);
               int[][] dp = new int[left.length()+1][right.length()+1];
               int A = dp.length;
               int B = dp[0].length;
               for(int i=0; i < A; i++)
                  Arrays.fill(dp[i], 2000);
               if(input.indexOf(left.charAt(0)) == -1 || input.indexOf(right.charAt(0)) == -1)
                  continue;
               dp[0][0] = 0;
               //dp[0][1] = input.indexOf(right.charAt(0))+1;
               //dp[1][0] = input.indexOf(left.charAt(0))+1;
               //dp[1][1] = Math.max(input.indexOf(left.charAt(0)), input.indexOf(right.charAt(0)))+1;
               for(int x=0; x <= left.length(); x++)
                  for(int y=0; y <= right.length(); y++)
                     if(dp[x][y] < 2000)
                     {
                        int dex = dp[x][y];
                        //add left
                        if(x+1 <= left.length())
                        {
                           char next = left.charAt(x);
                           TreeSet<Integer> find = bst[next-'a'];
                           if(find.size() > 0 && find.last() >= dex)
                           {
                              int newt = find.ceiling(dex);
                              dp[x+1][y] = Math.min(dp[x+1][y], newt+1);
                           }
                        }
                        //add right
                        if(y+1 <= right.length())
                        {
                           char next = right.charAt(y);
                           TreeSet<Integer> find = bst[next-'a'];
                           if(find.size() > 0 && find.last() >= dex)
                           {
                              int newt = find.ceiling(dex);
                              dp[x][y+1] = Math.min(dp[x][y+1], newt+1);
                           }
                        }
                     }
               if(dp[left.length()][right.length()] < 2000)
                  works = true;
            }
            //one step
            if(works || last(input, target, bst))
               System.out.println("YES");
            else
               System.out.println("NO");
         }
      }
      public static boolean last(String input, String target, TreeSet<Integer>[] bst)
      {
         int N = input.length();
         int M = target.length();
         if(bst[target.charAt(0)-'a'].size() == 0)
            return false;
         int dex = bst[target.charAt(0)-'a'].first()+1;
         for(int i=1; i < target.length(); i++)
         {
            if(bst[target.charAt(i)-'a'].size() == 0 || bst[target.charAt(i)-'a'].last() < dex)
               return false;
            dex = bst[target.charAt(i)-'a'].ceiling(dex)+1;
         }
         return true;
      }
   }