#1084 Common Permutation

124  1 s   128 MB  

Description

두 개의 문자열 $a$, $b$가 주어졌을 때 글자의 순서를 바꿔서 $a$의 부분 문자열로도 만들 수 있고 $b$의 부분 문자열로도 만들 수 있는 것 중 가장 긴 문자열 $x$를 출력하라. (문자열은 1000자 이내로 들어온다.)

Input

Test Case의 수 $T$가 입력된다.

각 Test Case에 대해 한 줄에 하나씩 두 줄에 걸쳐 문자열이 $2$개가 입력된다.

 

Output

입력된 각 Test Case마다 한 줄씩 $x$를 출력한다. 위의 조건을 만족하는 $x$가 여러개 있으면 알파벳 순으로 맨 앞에 있는 것을 출력한다.

 

Sample Input

Sample Output

3
pretty
women
walking
down
the
street
e
nw
et