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;
template <class T1, class T2>
void pr(const pair<T1, T2>& x);
template <class T, size_t SZ>
void pr(const array<T, SZ>& x);
template <class T>
void pr(const vector<T>& x);
template <class T>
void pr(const set<T>& x);
template <class T1, class T2>
void pr(const map<T1, T2>& x);
template <class T>
void pr(const T& x) {
  cout << x;
}
template <class Arg, class... Args>
void pr(const Arg& first, const Args&... rest) {
  pr(first);
  pr(rest...);
}
template <class T1, class T2>
void pr(const pair<T1, T2>& x) {
  pr("{", x.first, ", ", x.second, "}");
}
template <class T>
void prContain(const T& x) {
  pr("{");
  bool fst = 1;
  for (auto& a : x) pr(!fst ? ", " : "", a), fst = 0;
  pr("}");
}
template <class T, size_t SZ>
void pr(const array<T, SZ>& x) {
  prContain(x);
}
template <class T>
void pr(const vector<T>& x) {
  prContain(x);
}
template <class T>
void pr(const set<T>& x) {
  prContain(x);
}
template <class T1, class T2>
void pr(const map<T1, T2>& x) {
  prContain(x);
}
void ps() { pr("\n"); }
template <class Arg, class... Args>
void ps(const Arg& first, const Args&... rest) {
  pr(first, " ");
  ps(rest...);
}
template <typename T>
int remin(T& a, const T& b) {
  if (b < a) {
    a = b;
    return true;
  }
  return false;
}
template <typename T>
int remax(T& a, const T& b) {
  if (b > a) {
    a = b;
    return true;
  }
  return false;
}
int T;
int used[405];
string s, t;
int ns, nt, la;
vector<vector<int> > nxt;
bool calc(const string& a, const string& b) {
  int na = a.size(), nb = b.size();
  vector<vector<int> > dp(na + 1, vector<int>(nb + 1, 1E9));
  dp[0][0] = 0;
  for (int i = 0; i <= na; ++i) {
    for (int j = 0; j <= nb; ++j) {
      if (dp[i][j] > ns) continue;
      int len = dp[i][j];
      if (i < na && nxt[len][a[i] - 'a'] < 1E9) {
        remin(dp[i + 1][j], nxt[len][a[i] - 'a'] + 1);
      }
      if (j < nb && nxt[len][b[j] - 'a'] < 1E9) {
        remin(dp[i][j + 1], nxt[len][b[j] - 'a'] + 1);
      }
    }
  }
  return dp[na][nb] < 1E9;
}
int main(int argc, const char** argv) {
  cin >> T;
  for (int tt = 0; tt < T; ++tt) {
    cin >> s >> t;
    ns = s.size(), nt = t.size();
    bool ans = false;
    nxt.assign(ns + 1, vector<int>(26, 1E9));
    for (int i = ns - 1; i >= 0; --i) {
      nxt[i] = nxt[i + 1];
      nxt[i][s[i] - 'a'] = i;
    }
    for (int i = 0; i < nt; ++i) {
      if (calc(t.substr(0, i), t.substr(i, nt))) {
        ans = true;
        break;
      }
    }
    printf(ans ? "YES\n" : "NO\n");
  }
  return 0;
}
