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;
vector<long long int> primes;
void Sieve(long long int n) {
  vector<bool> prime(n + 1, true);
  for (long long int p = 2; p * p <= n; p++) {
    if (prime[p] == true) {
      for (long long int i = p * p; i <= n; i += p) prime[i] = false;
    }
  }
  for (long long int p = 2; p <= n; p++)
    if (prime[p]) primes.push_back(p);
}
long long int dnc(long long int bas, long long int power, long long int mod) {
  if (power == 0) return 1;
  if (power % 2 == 0) {
    int res = dnc(bas, power / 2, mod);
    return 1LL * res * res % mod;
  }
  return 1LL * bas * dnc(bas, power - 1, mod) % mod;
}
long long int f[2 * 300010 + 1], inv[2 * 300010 + 1];
void precalc() {
  f[0] = inv[0] = 1;
  for (long long int temp = 1; temp <= 2 * 300010; temp++) {
    f[temp] = 1ll * temp * f[temp - 1] % 10000007;
    inv[temp] = dnc(temp, 10000007 - 2, 10000007) * inv[temp - 1] % 10000007;
  }
}
long long int comb(long long int n, long long int k) {
  if (k > n || k < 0) return 0;
  return f[n] * inv[k] % 10000007 * inv[n - k] % 10000007;
}
bool solve(string q, string a, string b) {
  long long int p = q.size();
  long long int n = a.size();
  long long int m = b.size();
  vector<vector<long long int>> dp(n + 1,
                                   vector<long long int>(m + 1, 10000007));
  dp[0][0] = 0;
  vector<vector<long long int>> nxt(p + 1, vector<long long int>(26, -1));
  for (int i = p - 1; i >= 0; i--) {
    for (int j = 0; j < 26; j++) nxt[i][j] = nxt[i + 1][j];
    nxt[i][q[i] - 'a'] = i;
  }
  for (int j = 0; j <= n; j++) {
    for (int k = 0; k <= m; k++) {
      if (dp[j][k] == 10000007) continue;
      if (j < n && nxt[dp[j][k]][a[j] - 'a'] != -1)
        dp[j + 1][k] = min(dp[j + 1][k], nxt[dp[j][k]][a[j] - 'a'] + 1);
      if (k < m && nxt[dp[j][k]][b[k] - 'a'] != -1)
        dp[j][k + 1] = min(dp[j][k + 1], nxt[dp[j][k]][b[k] - 'a'] + 1);
    }
  }
  return dp[n][m] < 10000007;
}
int main() {
  long long int t;
  cin >> t;
  while (t--) {
    string q, r;
    cin >> q;
    cin >> r;
    string a, b;
    a = r;
    bool f = 0;
    for (int i = 0; i < r.size(); i++) {
      b = a[a.size() - 1] + b;
      a.pop_back();
      f = solve(q, a, b) || f;
    }
    if (f)
      cout << "YES";
    else
      cout << "NO";
    cout << endl;
  }
  return 0;
}
