해적왕의 보물을 찾기 위해 여행을 떠난 재우는 마침내 보물의 위치로 추정되는 알 수 없는 두 개의 문자열과 보물의 실마리가 될 만한 내용이 담긴 쪽지를 발견했습니다.
|
문자열 A가 1회 이상 반복되어 연결된 문자열이 B라고 하면, 문자열 A는 문자열 B를 나눌 수 있다고 말한다. (B = A + ... + A) ⇒ A는 B를 나눌 수 있다 뒷면에 적힌 두 개의 문자열을 나눌 수 있는 가장 긴 문자열을 찾아라, 이 세상 전부를 그곳에 두고 왔다. -해적왕- |
뒷면을 보니 긴 문자열 두개가 있었습니다. 보물을 찾기 위해서는 해적왕이 말한 대로 뒷면에 적혀 있는 두개의 문자열을 나눌 수 있는 가장 긴 문자열을 구해야 합니다.
입력의 개수 T(1<=T<=10)가 첫 줄에 주어지고, 그 다음 줄 부터 두 개의 문자열 L과 M이 주어집니다. 문자열 L과 M의 길이는 1 이상 1,000 이하이며, 알파벳 대문자로만 구성되어 있습니다.
입력된 두 개의 문자열을 나눌 수 있는 가장 긴 문자열을 구하여 출력합니다. 두 문자열을 나눌 수 없는 경우 빈 문자열("")을 출력합니다.
3
KOREATECHKOREATECH KOREATECHKOREATECHKOREATECH
BYEONGCHEON HONGCHEON
GURIGURIGURIGURI GURIGURI
KOREATECH
GURIGURI