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 <typename T>
inline bool uax(T &x, T y) {
  return (y > x) ? x = y, true : false;
}
template <typename T>
inline bool uin(T &x, T y) {
  return (y < x) ? x = y, true : false;
}
string to_string(char c) { return "'" + string(1, c) + "'"; }
string to_string(string s) { return '"' + s + '"'; }
string to_string(const char *s) { return to_string((string)s); }
template <typename A>
string to_string(A);
template <typename A, typename B>
string to_string(pair<A, B> p) {
  return "(" + to_string(p.first) + ": " + to_string(p.second) + ")";
}
template <typename A>
string to_string(A v) {
  bool f = false;
  string r = "{";
  for (auto x : v) {
    if (f) r += ", ";
    r += to_string(x);
    f = true;
  }
  return r += "}";
}
template <typename A>
string to_string(vector<vector<A>> v) {
  string r;
  for (auto x : v) r += "\n" + to_string(x);
  return r;
}
int Nerr;
template <typename A>
string to_string(A *p) {
  return to_string(vector<A>(p, p + Nerr));
}
void err(istream_iterator<string>) { cerr << endl; }
template <typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
  cerr << *it << " =: " << to_string(a) << "; ";
  err(++it, args...);
}
template <typename T>
void kek(T ans) {
  cout << ans << endl;
  exit(0);
}
int const MOD = 1e9 + 7;
long long const INF = 1e18 + 42;
int solve_case() {
  string s, t;
  cin >> s >> t;
  int n = int((s).size()), m = int((t).size());
  vector<array<int, 26>> nxt(n + 1);
  fill(begin(nxt.back()), end(nxt.back()), n);
  for (int i = n - 1; i >= 0; --i) {
    nxt[i] = nxt[i + 1];
    nxt[i][s[i] - 'a'] = i;
  }
  for (int p = 0; p < m; ++p) {
    int q = m - p;
    vector<vector<int>> dp(p + 1, vector<int>(q + 1, n + 1));
    dp[0][0] = 0;
    for (int i = 0; i <= p; ++i) {
      for (int j = 0; j <= q; ++j) {
        int pos = dp[i][j];
        if (pos >= n) continue;
        if (i < p) uin(dp[i + 1][j], nxt[pos][t[i] - 'a'] + 1);
        if (j < q) uin(dp[i][j + 1], nxt[pos][t[j + p] - 'a'] + 1);
      }
    }
    if (dp[p][q] <= n) return 1;
  }
  return 0;
}
int32_t main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  int tt;
  cin >> tt;
  while (tt--) {
    cout << (solve_case() ? "YES\n" : "NO\n");
  }
}
