Description

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

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

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

Input Format

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

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

Output Format

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

3
xyzdabc
xaybzc
abc
xyz
abbcd
aabbdcd

abc

abbcd

Hint

数据规模与约定

用 $|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$，输入字符串只含小写英文字母。