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>
char buf[1 << 23], *ps = buf, *pt = buf;
int read() {
  register int x = 0;
  register char f = 1, ch = (ps == pt && (pt = (ps = buf) +
                                               fread(buf, 1, 1 << 23, stdin),
                                          ps == pt)
                                 ? EOF
                                 : *ps++);
  for (; !isdigit(ch);
       ch = (ps == pt &&
                     (pt = (ps = buf) + fread(buf, 1, 1 << 23, stdin), ps == pt)
                 ? EOF
                 : *ps++))
    if (ch == '-') f ^= 1;
  for (; isdigit(ch);
       ch = (ps == pt &&
                     (pt = (ps = buf) + fread(buf, 1, 1 << 23, stdin), ps == pt)
                 ? EOF
                 : *ps++))
    x = (x << 1) + (x << 3) + (ch ^ '0');
  return f ? x : -x;
}
int read(char *s) {
  int n = 0;
  char ch =
      (ps == pt && (pt = (ps = buf) + fread(buf, 1, 1 << 23, stdin), ps == pt)
           ? EOF
           : *ps++);
  for (; isspace(ch) && ch != EOF;
       ch = (ps == pt &&
                     (pt = (ps = buf) + fread(buf, 1, 1 << 23, stdin), ps == pt)
                 ? EOF
                 : *ps++))
    ;
  for (; !isspace(ch) && ch != EOF;
       ch = (ps == pt &&
                     (pt = (ps = buf) + fread(buf, 1, 1 << 23, stdin), ps == pt)
                 ? EOF
                 : *ps++))
    s[n++] = ch;
  return s[n] = '\0', n;
}
char pbuf[1 << 23], *pp = pbuf;
struct __IO_flusher {
  ~__IO_flusher() { fwrite(pbuf, 1, pp - pbuf, stdout); }
} IO_flusher;
void print(int x, char ch = '\n') {
  if (x == 0)
    return (pp == pbuf + (1 << 23) ? fwrite(pbuf, 1, 1 << 23, stdout),
            pp = pbuf              : 0, *pp++ = '0'),
           (pp == pbuf + (1 << 23) ? fwrite(pbuf, 1, 1 << 23, stdout),
            pp = pbuf              : 0, *pp++ = ch),
           void(0);
  int cnt = 0, num[25];
  for (x < 0  ? (pp == pbuf + (1 << 23) ? fwrite(pbuf, 1, 1 << 23, stdout),
                pp = pbuf              : 0, *pp++ = '-'),
       x = -x : 0;
       x; x /= 10)
    num[++cnt] = x % 10;
  while (cnt)
    (pp == pbuf + (1 << 23) ? fwrite(pbuf, 1, 1 << 23, stdout), pp = pbuf : 0,
     *pp++ = num[cnt] ^ '0'),
        --cnt;
  (pp == pbuf + (1 << 23) ? fwrite(pbuf, 1, 1 << 23, stdout), pp = pbuf : 0,
   *pp++ = ch);
}
void print(const char *s, int n = -1, char ch = '\n') {
  if (n == -1) n = strlen(s);
  for (register int i = 0; i < n; ++i)
    (pp == pbuf + (1 << 23) ? fwrite(pbuf, 1, 1 << 23, stdout), pp = pbuf : 0,
     *pp++ = s[i]);
  (pp == pbuf + (1 << 23) ? fwrite(pbuf, 1, 1 << 23, stdout), pp = pbuf : 0,
   *pp++ = ch);
}
const int N = 405, INF = 0x3f3f3f3f;
int n, m, f[N][N];
char s[N], t[N];
void solve() {
  n = read(s + 1), m = read(t + 1);
  for (register int p = 1; p <= m; ++p) {
    for (register int i = 0; i <= n; ++i)
      for (register int j = 0; j <= p; ++j) f[i][j] = -INF;
    f[0][0] = 0;
    for (register int i = 1; i <= n; ++i)
      for (register int j = 0; j <= i && j <= p; ++j) {
        int k = f[i - 1][j];
        if (k >= 0) f[i][j] = k + (k <= m - p && s[i] == t[p + k + 1]);
        if (j && s[i] == t[j]) f[i][j] = std::max(f[i][j], f[i - 1][j - 1]);
      }
    if (f[n][p] == m - p) return print("YES"), void(0);
  }
  print("NO");
}
int main() {
  int T = read();
  while (T--) solve();
}
