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 T1, typename T2>
ostream& operator<<(ostream& os, pair<T1, T2> const& p) {
  return os << "<" << p.first << "," << p.second << ">";
}
template <typename... T>
ostream& operator<<(ostream& os, vector<T...> const& c) {
  if (c.empty()) return os << "{ }";
  auto iter = c.cbegin();
  os << "{ " << *iter;
  while (++iter != c.cend()) os << ", " << *iter;
  return os << " }";
};
template <typename... T>
ostream& operator<<(ostream& os, set<T...> const& c) {
  if (c.empty()) return os << "{ }";
  auto iter = c.cbegin();
  os << "{ " << *iter;
  while (++iter != c.cend()) os << ", " << *iter;
  return os << " }";
};
template <typename... T>
ostream& operator<<(ostream& os, map<T...> const& c) {
  if (c.empty()) return os << "{ }";
  auto iter = c.cbegin();
  os << "{ " << *iter;
  while (++iter != c.cend()) os << ", " << *iter;
  return os << " }";
};
void dbg() { cerr << endl; }
template <typename Head, typename... Tail>
void dbg(Head h, Tail... t) {
  cerr << " " << h;
  dbg(t...);
}
template <typename T>
T& minn(T& x, T const& y) {
  return x = min(x, y);
}
template <typename T>
T& maxx(T& x, T const& y) {
  return x = max(x, y);
}
constexpr int const mod = 1000000007;
constexpr int add(int a, int b) { return a + b < mod ? a + b : a + b - mod; }
constexpr int sub(int a, int b) { return a < b ? mod + a - b : a - b; }
constexpr int mul(int a, int b) { return 1LL * a * b % mod; }
template <typename... T>
constexpr int add(int a, int b, T... c) {
  return add(add(a, b), c...);
};
template <typename... T>
constexpr int sub(int a, int b, T... c) {
  return sub(sub(a, b), c...);
};
template <typename... T>
constexpr int mul(int a, int b, T... c) {
  return mul(mul(a, b), c...);
};
constexpr int square(int a) { return mul(a, a); }
constexpr int fpow(int a, int b) {
  return b ? mul(b & 1 ? a : 1, square(fpow(a, b >> 1))) : 1;
}
constexpr int const maxn = 512;
char s[maxn], t[maxn];
struct var_bitset {
  unsigned int bit32[16U], n;
  var_bitset() : n(16U) { memset(bit32, 0, 64); }
  void reset(unsigned int _n = 512U) {
    n = min(16U, (_n >> 5U) + !!(_n & 31U));
    memset(bit32, 0, n << 2);
  }
  void flip(unsigned int i) { bit32[i >> 5U] ^= 1U << (i & 31U); }
  unsigned int operator[](unsigned int i) const {
    return bit32[i >> 5U] >> (i & 31U);
  }
  var_bitset& operator|=(var_bitset const& other) {
    for (unsigned int i = 0; i != n; ++i) bit32[i] |= other.bit32[i];
    return *this;
  }
};
ostream& operator<<(ostream& os, var_bitset const& bs) {
  os << "n : " << bs.n;
  for (int i = 0; i < int(bs.n); ++i) os << " " << bs.bit32[i];
  return os;
}
bitset<maxn> dp[maxn][maxn];
var_bitset test0, test1;
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  test0.reset(64);
  test1.reset(64);
  0;
  0;
  test1.flip(1);
  test1.flip(3);
  test1.flip(5);
  test1.flip(7);
  test1.flip(9);
  test0 |= test1;
  0;
  0;
  int T;
  cin >> T;
  while (T--) {
    string s, t;
    cin >> s >> t;
    int n = t.size();
    for (int i = 0; i < int(n + 1); ++i)
      for (int j = i; j < int(n + 1); ++j) {
        dp[i][j].reset();
        if (!i) dp[i][j].flip(j);
      }
    for (char c : s) {
      for (int i = n; ~i; --i)
        for (int j = n; j >= i; --j) {
          if (i && t[i - 1] == c) dp[i][j] |= dp[i - 1][j];
          if (i != j && t[j - 1] == c) dp[i][j] |= dp[i][j - 1];
        }
    }
    bool ans = false;
    for (int i = 0; i < int(n + 1); ++i) ans |= dp[i][n][i];
    cout << (ans ? "YES" : "NO") << endl;
  }
}
