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>
#pragma GCC optimize("O2")
#pragma GCC optimize("tree-vectorize")
#pragma GCC target("sse4")
using namespace std;
using lint = long long;
using pii = pair<int, int>;
using pll = pair<lint, lint>;
template <typename T>
using vc = vector<T>;
template <typename T>
using vvc = vector<vector<T>>;
template <typename T>
inline bool chmax(T& a, T b) {
  if (a < b) {
    a = b;
    return true;
  }
  return false;
}
template <typename T>
inline bool chmin(T& a, T b) {
  if (a > b) {
    a = b;
    return true;
  }
  return false;
}
constexpr lint ten(int n) { return n == 0 ? 1 : ten(n - 1) * 10; }
class EEraseSubsequences {
 public:
  void solve(std::istream& in, std::ostream& out) {
    ios_base::sync_with_stdio(false);
    in.tie(nullptr), out.tie(nullptr);
    int tt;
    in >> tt;
    while (tt--) {
      string S, T;
      in >> S >> T;
      int N = (int)(S).size(), M = (int)(T).size();
      vvc<int> f(N + 1, vc<int>(26, N));
      for (int i = N - 1; 0 <= i; --i) {
        for (int j = (0); j < (26); ++j) f[i][j] = f[i + 1][j];
        f[i][S[i] - 'a'] = i;
      }
      bool ok = false;
      for (int i = (1); i < (M + 1); ++i) {
        string t1 = T.substr(0, i);
        string t2 = T.substr(i);
        vvc<int> dp(i + 1, vc<int>(M - i + 1, N + 1));
        dp[0][0] = 0;
        for (int j = (0); j < (i + 1); ++j)
          for (int k = (0); k < (M - i + 1); ++k) {
            if (dp[j][k] == N + 1) continue;
            if (j < i) chmin(dp[j + 1][k], f[dp[j][k]][t1[j] - 'a'] + 1);
            if (k < M - i) chmin(dp[j][k + 1], f[dp[j][k]][t2[k] - 'a'] + 1);
          }
        if (dp[i][M - i] != N + 1) {
          ok = true;
          break;
        }
      }
      if (ok)
        out << "YES\n";
      else
        out << "NO\n";
    }
  }
};
int main() {
  EEraseSubsequences solver;
  std::istream& in(std::cin);
  std::ostream& out(std::cout);
  solver.solve(in, out);
  return 0;
}
