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 java.io.BufferedWriter;
import java.io.DataInputStream;
import java.io.FileWriter;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.nio.file.Files;
import java.nio.file.Path;
import java.nio.file.Paths;

public class EErasingSubSequences {

	public static void main(String[] args) throws Exception {
		FastScanner sc = new FastScanner(System.in);
		FastPrinter out = new FastPrinter(System.out);
		EErasingSubSequences runner = new EErasingSubSequences();
		int T = sc.nextInt();
		for (int t = 0; t < T; t++) {
			runner.run(sc, out);
		}
		out.close();
	}

	int[] dp = new int[405];

	public void run(FastScanner sc, FastPrinter out) throws Exception {
		char[] input = sc.next().toCharArray();
		char[] arr = (sc.next() + " ").toCharArray();
		int N = arr.length - 1;
		for (int split = 1; split <= N; split++) {
			dp[0] = split;
			for (int i = 1; i <= N; i++) {
				dp[i] = -1;
			}
			for (int ii = 0; ii < input.length; ii++) {
				char cur = input[ii];
				for (int i = split; i >= 0; i--) {
					int p = dp[i];
					if (cur == arr[i]) {
						if (dp[i] > dp[i + 1]) {
							dp[i + 1] = dp[i];
						}
					}
					if (p != -1 && cur == arr[p]) {
						dp[i]++;
					}
				}
			}
			if (dp[split] == N) {
				out.println("YES");
				return;
			}
		}
		out.println("NO");
	}

	public void shuffle(int[] arr) {
		for (int i = 0; i < arr.length; i++) {
			int r = (int) (Math.random() * arr.length);
			if (i != r) {
				arr[i] ^= arr[r];
				arr[r] ^= arr[i];
				arr[i] ^= arr[r];
			}
		}
	}

	static class FastScanner {
		final private int BUFFER_SIZE = 1 << 10;
		private DataInputStream din;
		private byte[] buffer;
		private int bufferPointer, bytesRead;

		public FastScanner() {
			this(System.in);
		}

		public FastScanner(InputStream stream) {
			din = new DataInputStream(stream);
			buffer = new byte[BUFFER_SIZE];
			bufferPointer = bytesRead = 0;
		}

		public FastScanner(String fileName) throws IOException {
			Path p = Paths.get(fileName);
			buffer = Files.readAllBytes(p);
			bytesRead = buffer.length;
		}

		int[] nextIntArray(int N) throws IOException {
			int[] arr = new int[N];
			for (int i = 0; i < N; i++) {
				arr[i] = nextInt();
			}
			return arr;
		}

		String nextLine() throws IOException {
			int c = read();
			while (c != -1 && isEndline(c))
				c = read();
			if (c == -1) {
				return null;
			}
			StringBuilder res = new StringBuilder();
			do {
				if (c >= 0) {
					res.appendCodePoint(c);
				}
				c = read();
			} while (!isEndline(c));
			return res.toString();
		}

		boolean isEndline(int c) {
			return c == '\n' || c == '\r' || c == -1;
		}

		String next() throws Exception {
			int c = readOutSpaces();
			StringBuilder res = new StringBuilder();
			do {
				res.appendCodePoint(c);
				c = read();
			} while (!isSpaceChar(c));
			return res.toString();
		}

		boolean isSpaceChar(int c) {
			return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
		}

		public int nextInt() throws IOException {
			int ret = 0;
			byte c = read();
			while (c <= ' ')
				c = read();
			boolean neg = (c == '-');
			if (neg) c = read();
			do {
				ret = ret * 10 + c - '0';
			} while ((c = read()) >= '0' && c <= '9');

			if (neg) return -ret;
			return ret;
		}

		public long nextLong() throws IOException {
			long ret = 0;
			byte c = read();
			while (c <= ' ')
				c = read();
			boolean neg = (c == '-');
			if (neg) c = read();
			do {
				ret = ret * 10 + c - '0';
			} while ((c = read()) >= '0' && c <= '9');
			if (neg) return -ret;
			return ret;
		}

		public double nextDouble() throws IOException {
			double ret = 0, div = 1;
			byte c = read();
			while (c <= ' ')
				c = read();
			boolean neg = (c == '-');
			if (neg) c = read();

			do {
				ret = ret * 10 + c - '0';
			} while ((c = read()) >= '0' && c <= '9');

			if (c == '.') {
				while ((c = read()) >= '0' && c <= '9') {
					ret += (c - '0') / (div *= 10);
				}
			}

			if (neg) return -ret;
			return ret;
		}

		private void fillBuffer() throws IOException {
			if (din == null) {
				bufferPointer = 0;
				bytesRead = -1;
			} else {
				bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);
			}
			if (bytesRead == -1) buffer[0] = -1;
		}

		private byte read() throws IOException {
			if (bufferPointer == bytesRead) fillBuffer();
			return buffer[bufferPointer++];
		}

		private int readOutSpaces() throws IOException {
			while (true) {
				if (bufferPointer == bytesRead) fillBuffer();
				int c = buffer[bufferPointer++];
				if (!isSpaceChar(c)) {
					return c;
				}
			}
		}

		public void close() throws IOException {
			if (din == null) return;
			din.close();
		}

		public int[][] readGraph(int N, int M, boolean zeroIndexed, boolean bidirectional) throws Exception {
			int[][] adj = new int[N][];
			int[] numNodes = new int[N];
			int[][] input = new int[M][2];
			for (int i = 0; i < M; i++) {
				int a = nextInt();
				int b = nextInt();
				if (zeroIndexed) {
					a--;
					b--;
				}
				input[i][0] = a;
				input[i][1] = b;
				numNodes[a]++;
				if (bidirectional) numNodes[b]++;
			}
			for (int i = 0; i < N; i++) {
				adj[i] = new int[numNodes[i]];
				numNodes[i] = 0;
			}
			for (int i = 0; i < M; i++) {
				int a = input[i][0];
				int b = input[i][1];
				adj[a][numNodes[a]++] = b;
				if (bidirectional) adj[b][numNodes[b]++] = a;
			}
			return adj;
		}

		public int[][][] readWeightedGraph(int N, int M, boolean zeroIndexed, boolean bidirectional) throws Exception {
			int[][][] adj = new int[N][][];
			int[] numNodes = new int[N];
			int[][] input = new int[M][3];
			for (int i = 0; i < M; i++) {
				int a = nextInt();
				int b = nextInt();
				if (zeroIndexed) {
					a--;
					b--;
				}
				int d = nextInt();
				input[i][0] = a;
				input[i][1] = b;
				input[i][2] = d;
				numNodes[a]++;
				if (bidirectional) numNodes[b]++;
			}
			for (int i = 0; i < N; i++) {
				adj[i] = new int[numNodes[i]][2];
				numNodes[i] = 0;
			}
			for (int i = 0; i < M; i++) {
				int a = input[i][0];
				int b = input[i][1];
				int d = input[i][2];
				adj[a][numNodes[a]][0] = b;
				adj[a][numNodes[a]][1] = d;
				numNodes[a]++;
				if (bidirectional) {
					adj[b][numNodes[b]][0] = a;
					adj[b][numNodes[b]][1] = d;
					numNodes[b]++;
				}
			}
			return adj;
		}
	}

	static class FastPrinter {
		static final char ENDL = '\n';
		StringBuilder buf;
		PrintWriter pw;

		public FastPrinter(OutputStream stream) {
			buf = new StringBuilder();
			pw = new PrintWriter(new BufferedWriter(new OutputStreamWriter(stream)));
		}

		public FastPrinter(String fileName) throws Exception {
			buf = new StringBuilder();
			pw = new PrintWriter(new BufferedWriter(new FileWriter(fileName)));
		}

		public FastPrinter(StringBuilder buf) {
			this.buf = buf;
		}

		public void print(int a) {
			buf.append(a);
		}

		public void print(long a) {
			buf.append(a);
		}

		public void print(char a) {
			buf.append(a);
		}

		public void print(char[] a) {
			buf.append(a);
		}

		public void print(double a) {
			buf.append(a);
		}

		public void print(String a) {
			buf.append(a);
		}

		public void print(Object a) {
			buf.append(a.toString());
		}

		public void println() {
			buf.append(ENDL);
		}

		public void println(int a) {
			buf.append(a);
			buf.append(ENDL);
		}

		public void println(long a) {
			buf.append(a);
			buf.append(ENDL);
		}

		public void println(char a) {
			buf.append(a);
			buf.append(ENDL);
		}

		public void println(char[] a) {
			buf.append(a);
			buf.append(ENDL);
		}

		public void println(double a) {
			buf.append(a);
			buf.append(ENDL);
		}

		public void println(String a) {
			buf.append(a);
			buf.append(ENDL);
		}

		public void println(Object a) {
			buf.append(a.toString());
			buf.append(ENDL);
		}

		public void printf(String format, Object... args) {
			buf.append(String.format(format, args));
		}

		public void close() {
			pw.print(buf);
			pw.close();
		}

		public void flush() {
			pw.print(buf);
			pw.flush();
			buf.setLength(0);
		}

	}

}