Жақында зерттеушілер Наурыз көженің екі көне жазбасын тапты. Бұл тағам қазанда дайындалады: ингредиенттер қазанға бірінен кейін бірі, қадам-қадаммен салынады. Екі жазбада да ингредиенттер қазанға салыну ретімен берілген.

Ыңғайлы болу үшін әр ингредиент латын әліпбиінің бір кіші әрпімен белгіленеді, сондықтан әр жазба әріптер тізбегі түрінде беріледі.

Егер \(S\) рецептісінен бірнеше қадамды (мүмкін, бірде-бір қадамды да өшірмей), қалғандарының ретін өзгертпей, дәл \(T\) рецептін алуға болса, онда \(S\) рецепті \(T\) рецептінің үсті рецепті деп аталады. Бұл жағдайда \(T\) рецепті \(S\) рецептінің ішкі тізбегі деп аталады.

Егер \(S\) рецепті \(A\) және \(B\) рецепттерінің екеуіне де үсті рецепт болса, онда ол олардың ортақ үсті рецепті деп аталады.

\(A\) және \(B\) рецепттерінің ортақ үсті рецепті \(S\) идеал рецепт деп аталады, егер одан бірде-бір қадамды өшіріп, алынған жазбаны \(A\) мен \(B\) үшін де ортақ үсті рецепт күйінде қалдыру мүмкін болмаса.

Басқаша айтқанда, идеал рецепт тек қажетті қадамдардан тұрады: егер кез келген бір қадамды алып тастасақ, ол не \(A\) рецептінің, не \(B\) рецептінің үсті рецепті болудан қалады.

Сіздің міндетіңіз — берілген \(A\) және \(B\) екі жазба бойынша кез келген идеал рецептті қалпына келтіру.

Назар аударыңыз: жауаптың мүмкін болған ең қысқа болуы талап етілмейді.

Мысалы, \(A = aab\) және \(B = baa\) болса, 'baab' және 'aabaa' жазбаларының екеуі де идеал рецепт болады, бірақ олардың ұзындықтары әртүрлі.

Енгізу

Бірінші жолда тестер саны \(T\) беріледі (\(1 \le T \le 10^5\)).

Келесі \(T\) жолдың әрқайсысында бос орын арқылы \(A\) және \(B\) рецепт жазбалары берілген (\(1 \le |A|, |B| \le 10^5\)). Олар латын әліпбиінің кіші әріптерінен тұрады.

Кіріс деректеріндегі барлық жазбалардың ұзындықтарының қосындысы \(2 \cdot 10^5\)-тен аспайтынына кепілдік беріледі.

Шығару

Әрбір тест үшін жеке жолға \(A\) және \(B\) үшін кез келген идеал рецептті шығарыңыз.

Егер бірнеше дұрыс жауап болса, олардың кез келгенін шығарыңыз.

Мысалдар

Енгізу 1

7
aab baa
a a
a b
ab ab
ab ba
ab ac
aaaa aaaa

Жауап 1

aabaa
a
ab
ab
aba
abc
aaaa