为了让你的钱更充裕，比起赚更多的钱，减少开支要容易得多。

Junpei 是一家会员制餐厅的经理。由于疫情的影响，餐厅无法负担过于庞大的美味菜肴菜单。因此，如何缩减菜单同时保留特色菜品成了一个问题。

菜单可以看作是一个仅包含小写英文字母和数字的字符串 $S$，Junpei 认为餐厅的核心特色是一个字符串 $F$，且目前 $F$ 是 $S$ 的一个子序列。为了缩减菜单，你可以将 $S$ 缩减为其一个子串 $S'$，同时要求 $F$ 仍是 $S'$ 的子序列。

Junpei 请你找出满足该要求且长度最短的 $S$ 的子串 $S'$。

对于那些对子序列和子串的定义感到好奇的人，考虑两个非空字符串 $A, B$：

• 如果称 $A$ 是 $B$ 的子序列，意味着我们可以找到一组 $|A|$ 个下标 $\{i_k\}$，满足 $1 \le i_1 < i_2 < \dots < i_{|A|} \le |B|$，使得 $A = B_{i_1}B_{i_2}\dots B_{i_{|A|}}$。
• 如果称 $A$ 是 $B$ 的子串，意味着我们可以从 $B$ 中删去一个（可能为空的）前缀和一个（可能为空的）后缀来得到 $A$。

输入格式

第一行包含一个整数 $T$ ($1 \le T \le 10^4$)，表示测试用例的数量。

对于每个测试用例，包含一行，由两个字符串 $S, F$ ($1 \le |S| \le 10^5, 1 \le |F| \le 100$) 组成，中间用空格隔开。保证 $F$ 是 $S$ 的子序列，且两个字符串均仅包含小写英文字母（'a' 到 'z'）和数字（'0' 到 '9'）。

保证所有测试用例的 $|S|$ 之和不超过 $5 \times 10^5$。

输出格式

对于每个测试用例，输出一行，表示包含 $F$ 的最短 $S$ 的子串。如果存在多个答案，输出其中任意一个即可。

样例

输入 1

4
114514 15
shanghaicpc ac
aaabbbaaabbbccc abc
howdeliciousandfreshitis oishii

输出 1

145
aic
abbbc
owdeliciousandfreshiti