You have a string s and a chip, which you can place onto any character of this string. 

After placing the chip, you move it to the right several (maybe zero) times, i. e. you perform the following operation several times: if the current position of the chip is i, you move it to the position i + 1. Of course, moving the chip to the right is impossible if it is already in the last position.

After moving the chip to the right, you move it to the left several (maybe zero) times, i. e. you perform the following operation several times: if the current position of the chip is i, you move it to the position i - 1. Of course, moving the chip to the left is impossible if it is already in the first position.

When you place a chip or move it, you write down the character where the chip ends up after your action. For example, if s is abcdef, you place the chip onto the 3-rd character, move it to the right 2 times and then move it to the left 3 times, you write down the string cdedcb.

You are given two strings s and t. Your task is to determine whether it's possible to perform the described operations with s so that you write down the string t as a result.

Input

The first line contains one integer q (1 ≤ q ≤ 500) — the number of test cases.

Each test case consists of two lines. The first line contains the string s (1 ≤ |s| ≤ 500), the second line contains the string t (1 ≤ |t| ≤ 2 ⋅ |s| - 1). Both strings consist of lowercase English characters.

It is guaranteed that the sum of |s| over all test cases does not exceed 500.

Output

For each test case, print "YES" if you can obtain the string t by performing the process mentioned in the statement with the string s, or "NO" if you cannot.

You may print each letter in any case (YES, yes, Yes will all be recognized as positive answer, NO, no and nO will all be recognized as negative answer).

Example

Input


6
abcdef
cdedcb
aaa
aaaaa
aab
baaa
ab
b
abcdef
abcdef
ba
baa


Output


YES
YES
NO
YES
YES
NO

Note

Consider the examples.

The first test case is described in the statement.

In the second test case, you can place the chip on the 1-st position, move it twice to the right, and then move it twice to the left.

In the fourth test case, you can place the chip on the 2-nd position, and then don't move it at all.

In the fifth test case, you can place the chip on the 1-st position, move it 5 times to the right, and then finish the process.
# Problem: B. Reverse String
# Contest: Codeforces - Harbour.Space Scholarship Contest 2021-2022 (open for everyone, rated, Div. 1 + Div. 2)
# URL: https://codeforces.com/contest/1553/problem/B
# Memory Limit: 256 MB
# Time Limit: 3000 ms
# 
# Powered by CP Editor (https://cpeditor.org)

# ____           ____   ___         # skeon19
#|      | /     |      |   | |\   | # 
#|____  |/      |___   |   | | \  | # EON_KID
#     |	|\      |      |   | |  \ | #
# ____|	| \ ___ |____  |___| |   \| # Soul_Silver

from collections import defaultdict
import sys,io,os
INP=sys.stdin.readline
inp=lambda:[*map(int,INP().encode().split())]
sinp=lambda:[*map(str,INP().split())]
out=sys.stdout.write
#from functools import reduce
#from bisect import bisect_right,bisect_left
#from sortedcontainers import SortedList, SortedSet, SortedDict
#import sympy #Prime number library
#import heapq
#Maxint=9223372036854775807

def main():
    for _ in range(inp()[0]):
        l=list(input())
        a=list(input())
        j=0;m=0
        check=0
        while m <len(l) and j<len(a):
        	if l[m]==a[j]:
        		i=m
        		while m<len(l) and j<len(a):
        			if l[m]==a[j]:
        				k=m-1;r=j+1
        				while k>-1 and r<len(a):
        					if l[k]==a[r]:
        						k-=1
        						r+=1
        					else:
        						break
        				if r==len(a):
        					check=1
        					break
        				m+=1;j+=1
        			else:
        				break
        		if j==len(a) or check:
        			check=1
        			break
        		m=i;j=0
        	if check:
        		break
        	m+=1
        if check or j==len(a):
        	print("YES")
        else:
        	print("NO")
        	
        		
        	

        		
        		
        
        
        
        
        
###############################################################       
def SumOfExpOfFactors(a):
	fac = 0
	lis=SortedList()
	if not a&1: 
		lis.add(2)
	while not a&1:
		a >>= 1
		fac += 1
	for i in range(3,int(a**0.5)+1,2):
		if not a%i:
			lis.add(i)
		while not a%i:
			a //= i
			fac += 1
	if a != 1:
		lis.add(a)
		fac += 1
	return fac,lis
###############################################################
div=[0]*(1000001)
def NumOfDivisors(n): #O(nlog(n))
	for i in range(1,n+1):
		for j in range(i,n+1,i):
			div[j]+=1
###############################################################
def primes1(n): #return a list having prime numbers from 2 to n
    """ Returns  a list of primes < n """
    sieve = [True] * (n//2)
    for i in range(3,int(n**0.5)+1,2):
        if sieve[i//2]:
            sieve[i*i//2::i] = [False] * ((n-i*i-1)//(2*i)+1)
    return [2] + [2*i+1 for i in range(1,n//2) if sieve[i]]
##############################################################    
def GCD(a,b):
    if(b==0):
        return a
    else:
        return GCD(b,a%b)
##############################################################
#
#     1
#   /   \
#  2     3
# /\   / \ \ \
#4  5  6 7 8 9
#      \
#      10

class Graph:
    def __init__(self):
        self.Graph = defaultdict(list)
        
    def addEdge(self, u, v):
        self.Graph[u].append(v)
        self.Graph[v].append(u)
    #DFS Graph / tree    
    def DFSUtil(self, v, visited):
        visited.add(v)
        #print(v, end=' ')
        for neighbour in self.Graph[v]:
            if neighbour not in visited: #not needed if its a tree
                self.DFSUtil(neighbour, visited)
    def DFS(self, v):
 
        visited = set() #not needed if its a tree
        self.DFSUtil(v, visited) #Visited not needed if its a tree
    #BFS Graph / tree
    def BFS(self, s):
        # Mark all the vertices as not visited
        
        visited = set()
        # Create a queue for BFS
        queue = []
        queue.append(s)
        visited.add(s)
        while queue:
            s = queue.pop(0)
            #print (s, end = " ")
            for i in self.Graph[s]:
                if i not in visited:
                    queue.append(i)
                    visited.add(i)
'''
g = Graph()
g.addEdge(1, 2)
g.addEdge(1, 3)
g.addEdge(2, 4)
g.addEdge(2, 5)
g.addEdge(3, 6)
g.addEdge(3, 7)
g.addEdge(3, 8)
g.addEdge(3, 9)
g.addEdge(6,10)
g.DFS(1)  
g.BFS(1)  '''   
##############################################################
class SortedList:
    def __init__(self, iterable=[], _load=200):
        """Initialize sorted list instance."""
        values = sorted(iterable)
        self._len = _len = len(values)
        self._load = _load
        self._lists = _lists = [values[i:i + _load] for i in range(0, _len, _load)]
        self._list_lens = [len(_list) for _list in _lists]
        self._mins = [_list[0] for _list in _lists]
        self._fen_tree = []
        self._rebuild = True

    def _fen_build(self):
        """Build a fenwick tree instance."""
        self._fen_tree[:] = self._list_lens
        _fen_tree = self._fen_tree
        for i in range(len(_fen_tree)):
            if i | i + 1 < len(_fen_tree):
                _fen_tree[i | i + 1] += _fen_tree[i]
        self._rebuild = False

    def _fen_update(self, index, value):
        """Update `fen_tree[index] += value`."""
        if not self._rebuild:
            _fen_tree = self._fen_tree
            while index < len(_fen_tree):
                _fen_tree[index] += value
                index |= index + 1

    def _fen_query(self, end):
        """Return `sum(_fen_tree[:end])`."""
        if self._rebuild:
            self._fen_build()

        _fen_tree = self._fen_tree
        x = 0
        while end:
            x += _fen_tree[end - 1]
            end &= end - 1
        return x

    def _fen_findkth(self, k):
        """Return a pair of (the largest `idx` such that `sum(_fen_tree[:idx]) <= k`, `k - sum(_fen_tree[:idx])`)."""
        _list_lens = self._list_lens
        if k < _list_lens[0]:
            return 0, k
        if k >= self._len - _list_lens[-1]:
            return len(_list_lens) - 1, k + _list_lens[-1] - self._len
        if self._rebuild:
            self._fen_build()

        _fen_tree = self._fen_tree
        idx = -1
        for d in reversed(range(len(_fen_tree).bit_length())):
            right_idx = idx + (1 << d)
            if right_idx < len(_fen_tree) and k >= _fen_tree[right_idx]:
                idx = right_idx
                k -= _fen_tree[idx]
        return idx + 1, k

    def _delete(self, pos, idx):
        """Delete value at the given `(pos, idx)`."""
        _lists = self._lists
        _mins = self._mins
        _list_lens = self._list_lens

        self._len -= 1
        self._fen_update(pos, -1)
        del _lists[pos][idx]
        _list_lens[pos] -= 1

        if _list_lens[pos]:
            _mins[pos] = _lists[pos][0]
        else:
            del _lists[pos]
            del _list_lens[pos]
            del _mins[pos]
            self._rebuild = True

    def _loc_left(self, value):
        """Return an index pair that corresponds to the first position of `value` in the sorted list."""
        if not self._len:
            return 0, 0

        _lists = self._lists
        _mins = self._mins

        lo, pos = -1, len(_lists) - 1
        while lo + 1 < pos:
            mi = (lo + pos) >> 1
            if value <= _mins[mi]:
                pos = mi
            else:
                lo = mi

        if pos and value <= _lists[pos - 1][-1]:
            pos -= 1

        _list = _lists[pos]
        lo, idx = -1, len(_list)
        while lo + 1 < idx:
            mi = (lo + idx) >> 1
            if value <= _list[mi]:
                idx = mi
            else:
                lo = mi

        return pos, idx

    def _loc_right(self, value):
        """Return an index pair that corresponds to the last position of `value` in the sorted list."""
        if not self._len:
            return 0, 0

        _lists = self._lists
        _mins = self._mins

        pos, hi = 0, len(_lists)
        while pos + 1 < hi:
            mi = (pos + hi) >> 1
            if value < _mins[mi]:
                hi = mi
            else:
                pos = mi

        _list = _lists[pos]
        lo, idx = -1, len(_list)
        while lo + 1 < idx:
            mi = (lo + idx) >> 1
            if value < _list[mi]:
                idx = mi
            else:
                lo = mi

        return pos, idx

    def add(self, value):
        """Add `value` to sorted list."""
        _load = self._load
        _lists = self._lists
        _mins = self._mins
        _list_lens = self._list_lens

        self._len += 1
        if _lists:
            pos, idx = self._loc_right(value)
            self._fen_update(pos, 1)
            _list = _lists[pos]
            _list.insert(idx, value)
            _list_lens[pos] += 1
            _mins[pos] = _list[0]
            if _load + _load < len(_list):
                _lists.insert(pos + 1, _list[_load:])
                _list_lens.insert(pos + 1, len(_list) - _load)
                _mins.insert(pos + 1, _list[_load])
                _list_lens[pos] = _load
                del _list[_load:]
                self._rebuild = True
        else:
            _lists.append([value])
            _mins.append(value)
            _list_lens.append(1)
            self._rebuild = True

    def discard(self, value):
        """Remove `value` from sorted list if it is a member."""
        _lists = self._lists
        if _lists:
            pos, idx = self._loc_right(value)
            if idx and _lists[pos][idx - 1] == value:
                self._delete(pos, idx - 1)

    def remove(self, value):
        """Remove `value` from sorted list; `value` must be a member."""
        _len = self._len
        self.discard(value)
        if _len == self._len:
            raise ValueError('{0!r} not in list'.format(value))

    def pop(self, index=-1):
        """Remove and return value at `index` in sorted list."""
        pos, idx = self._fen_findkth(self._len + index if index < 0 else index)
        value = self._lists[pos][idx]
        self._delete(pos, idx)
        return value

    def bisect_left(self, value):
        """Return the first index to insert `value` in the sorted list."""
        pos, idx = self._loc_left(value)
        return self._fen_query(pos) + idx

    def bisect_right(self, value):
        """Return the last index to insert `value` in the sorted list."""
        pos, idx = self._loc_right(value)
        return self._fen_query(pos) + idx

    def count(self, value):
        """Return number of occurrences of `value` in the sorted list."""
        return self.bisect_right(value) - self.bisect_left(value)

    def __len__(self):
        """Return the size of the sorted list."""
        return self._len

    def __getitem__(self, index):
        """Lookup value at `index` in sorted list."""
        pos, idx = self._fen_findkth(self._len + index if index < 0 else index)
        return self._lists[pos][idx]

    def __delitem__(self, index):
        """Remove value at `index` from sorted list."""
        pos, idx = self._fen_findkth(self._len + index if index < 0 else index)
        self._delete(pos, idx)

    def __contains__(self, value):
        """Return true if `value` is an element of the sorted list."""
        _lists = self._lists
        if _lists:
            pos, idx = self._loc_left(value)
            return idx < len(_lists[pos]) and _lists[pos][idx] == value
        return False

    def __iter__(self):
        """Return an iterator over the sorted list."""
        return (value for _list in self._lists for value in _list)

    def __reversed__(self):
        """Return a reverse iterator over the sorted list."""
        return (value for _list in reversed(self._lists) for value in reversed(_list))

    def __repr__(self):
        """Return string representation of sorted list."""
        return 'SortedList({0})'.format(list(self))
    # https://github.com/cheran-senthil/PyRival/blob/master/pyrival/data_structures/SortedList.py
###################################################################################################

if __name__ == '__main__':
    main()