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
import sys
range = xrange
input = raw_input

t = int(input())
for _ in range(t):
    S = [ord(c) - ord('a') for c in input()]
    T = [ord(c) - ord('a') for c in input()]

    n = len(S)
    m = len(T)

    buckets = [[n] for _ in range(26)]
    for i in reversed(range(n)):
        buckets[S[i]].append(i)

    for l in range(0, m + 1):
        # dp[i][j] = min k such that S[:k] can be used to match T[:i], T[l:j]
        A = l + 1
        B = m - l + 1

        dp = [n]*(A * B)
        buckets_copy = [list(b) for b in buckets]
        last_letter = [b[-1] for b in buckets_copy]
        
        state_buckets = [[] for _ in range(n + 2)]
        state_buckets[-1].append(0)
        for i in range(-1, n):
            if i >= 0: 
                buckets_copy[S[i]].pop()
                last_letter[S[i]] = buckets_copy[S[i]][-1]
            
            for ind in state_buckets[i]:
                if dp[ind] > i:
                    dp[ind] = i
                    
                    b,a = divmod(ind, A)
                    if a < l:
                        state_buckets[last_letter[T[a]]].append(ind + 1)
                    if l + b < m:
                        state_buckets[last_letter[T[l + b]]].append(ind + A)

        if dp[-1] != n:
            print 'YES'
            break
    else:
        print 'NO'

