TRIP - Trip

Alice and Bob want to go on holiday. Each of them has drawn up a list of cities to be visited in turn. A list may contain a city more than once. As they want to travel together, they have to agree upon a common route. No one wants to change the order of the cities on his list or add other cities. Therefore they have no choice but to remove some cities from the list. Of course the common route is to involve as much sight-seeing in cities as possible. There are exactly 26 cities in the region. Therefore they are encoded on the lists as lower case letters from 'a' to 'z'.

Input

The first line of input contains a number T <= 10 that indicates the number of test cases to follow. Each test case consists of two lines; the first line is the list of Alice, the second line is the list of Bob. Each list consists of 1 to 80 lower case letters.

Output

The output for each test case should contain all different trips exactly once that meet the conditions described above. There is at least one such trip, but never more than 1000 different ones. You should order the trips in lexicographic order. Print one blank line between the output of different test cases.

Example

Input

1
abcabcaa
acbacba

Output

ababa
abaca
abcba
acaba
acaca
acbaa
acbca

Added by:Adrian Kuegel
Date:2004-06-05
Time limit:3s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: NODEJS OBJC PERL6 SQLITE VB.NET
Resource:own problem, used in CEOI 2003

hide comments
2011-02-07 09:29:54 Adrian Kuegel
It refers to the trips counted without duplicates ("but never more than 1000 different ones").
2011-02-06 21:28:49 Aditya A R
are the duplicates included in the 1000 different trips or the 1000 only refers to the trips counted without duplicates?
please reply soon.....thank u!
2010-12-01 22:14:39 islCodr
can compare 'apples' and 'oranges'
2010-02-24 14:50:42 Farshad soleimani asl
Yeah! so enjoyable trip...
A travel with character destinations!
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.