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
#include <bits/stdc++.h>
using namespace std;
int read() {
  int res = 0, f = 1;
  char c = getchar();
  while (!isdigit(c) && c != '-') c = getchar();
  if (c == '-') f = -1, c = getchar();
  while (isdigit(c)) res = (res << 3) + (res << 1) + (c ^ 48), c = getchar();
  return res * f;
}
const int maxn = 4e2 + 10;
int s[maxn], t[maxn];
int lens, lent, lena, lenb;
int nt[30][maxn], dp[maxn][maxn];
void cle() {
  memset(nt, 63, sizeof(nt));
  return;
}
void in(int aa[], int &ll) {
  char c = getchar();
  ll = 0;
  while (isalpha(c)) aa[++ll] = c - 'a' + 1, c = getchar();
  return;
}
int work() {
  memset(dp, 63, sizeof(dp));
  dp[0][0] = 0;
  for (int i = 0; i <= lena; i++)
    for (int j = 0; j <= lenb; j++)
      if (dp[i][j] < lens) {
        if (i < lena)
          dp[i + 1][j] = min(dp[i + 1][j], nt[t[i + 1]][dp[i][j] + 1]);
        if (j < lenb)
          dp[i][j + 1] = min(dp[i][j + 1], nt[t[lena + j + 1]][dp[i][j] + 1]);
      }
  return dp[lena][lenb] <= lens;
}
int main() {
  int T = read();
  while (T--) {
    cle();
    in(s, lens);
    in(t, lent);
    for (int i = 1; i <= 26; i++)
      for (int j = lens; j; j--) nt[i][j] = (s[j] == i) ? j : nt[i][j + 1];
    int flag = 0;
    for (lena = 1; lena <= lent; lena++) {
      lenb = lent - lena;
      if (work()) {
        printf("YES\n");
        flag = 1;
        break;
      }
    }
    if (!flag) printf("NO\n");
  }
  return 0;
}
