题目背景

在本题中，我们称一个串 $x$ 是一个串 $y$ 的子串当且仅当在 $y$ 开头和结尾删除若干个（可以为 $0$ 个）字符后得到的字符串与 $x$ 相同。例如，$\texttt{bc}$,$\texttt{abc}$,$\texttt{a}$,$\texttt{abcd}$ 都是字符串 $\texttt{abcd}$ 的子串，但 $\texttt{abd}$ 不是。

我们称一个串 $x$ 是一个串 $y$ 的子序列当且仅当在 $y$ 中删除若干个（可以为 $0$ 个）字符后得到的字符串与 $x$ 相同。例如，$\texttt{bc}$,$\texttt{abc}$,$\texttt{a}$,$\texttt{abcd}$,$\texttt{abd}$ 都是字符串 $\texttt{abcd}$ 的子串，但 $\texttt{dcba}$ 不是。

特别的，空串是任何串的子串，也是任何串的子序列。

题目描述

给定两个字符串 $s,t$，扶苏想让你求出一个字符串 $x$，满足：

• $x$ 是 $s$ 的子串。
• $x$ 是 $t$ 的子序列。
• 在所有满足前述两条的字符串中，$x$ 的长度最长。
• 在所有满足前述三条的字符串中，$x$ 的字典序最小。

请你帮她求出这样的字符串 $x$。

输入格式

本题单个测试点内有多组测试数据，第一行是一个整数，表示数据组数 $T$。

对每组数据，输入两行，每行一个字符串，依次表示 $s$ 和 $t$。

输出格式

对每组数据，输出一行一个字符串，表示你找到的 $x$。
特别的，如果 $x$ 是空串，你需要输出一个空行。

3
xyzdabc
xaybzc
abc
xyz
abbcd
aabbdcd

abc

abbcd

提示

数据规模与约定

用 $|x|$ 表示字符串 $x$ 的长度。

• 对 $10\%$ 的数据，$T = 0$。
• 对 $30\%$ 的数据，$|s| = 1$。
• 对 $50\%$ 的数据，$|s|, |t| \leq 10$。
• 对 $80\%$ 的数据，$|s|, |t| \leq 100$。
• 对 $100\%$ 的数据，保证 $0 \leq T \leq 10$，$1 \leq |s|\leq 10^3$，$1 \leq |t| \leq 10^5$，输入字符串只含小写英文字母。