암호 추정

단일 치환 암호는 영어 대문자마다 바꿀 영어 대문자 하나를 정한 뒤, 단어의 각 글자를 정해진 글자로 바꾸는 암호이다. 암호화하기 전의 단어를 평문 단어, 암호화한 뒤의 단어를 암호문 단어라고 한다.

글자를 바꾸는 규칙은 다음 두 조건을 만족해야 한다.

• 같은 글자는 항상 같은 글자로 바뀐다.
• 서로 다른 글자는 서로 다른 글자로 바뀐다.

어떤 글자가 자기 자신으로 바뀌는 것도 허용한다. 글자의 순서와 단어의 길이는 바뀌지 않는다.

예를 들어, A를 X로, B를 Y로 바꾸면 ABBA는 XYYX가 된다. ABBA가 XYYY로 바뀌는 것은 같은 글자 A가 서로 다른 글자로 바뀌므로 불가능하다. ABBA가 XXXX로 바뀌는 것도 서로 다른 글자 A와 B가 같은 글자로 바뀌므로 불가능하다.

다다스는 $N$개의 단어 $C_1,C_2,\ldots,C_N$으로 이루어진 암호문과, 암호문에 자주 등장할 것으로 예상되는 평문 단어 $S$를 알고 있다. 하지만 어떤 글자가 어떤 글자로 바뀌었는지는 모른다.

위 규칙을 만족하는 어떤 치환을 사용하여 $S$를 바꾼 결과가 될 수 있는 단어를 후보 단어라고 한다. 후보를 판단할 때는 각 단어에 가능한 치환이 있는지 독립적으로 확인한다. 모든 후보 단어에 같은 치환을 사용할 필요는 없다.

다다스는 후보 단어마다 암호문에 등장한 횟수를 세고, 가장 많이 등장한 단어를 $S$의 치환 결과라고 추정한다. 등장 횟수가 같은 후보 단어가 여러 개라면 사전순으로 가장 앞서는 단어를 선택한다. 사전순으로 비교할 때는 왼쪽부터 처음으로 다른 글자를 찾아, 그 글자가 알파벳 순서로 앞서는 단어를 선택한다. 예를 들어 ABCA와 XYZX가 각각 두 번 등장한 후보라면 ABCA를 선택한다.

암호문과 $S$가 주어질 때, 다다스가 추정한 단어를 구하여라. 후보 단어가 하나도 없다면 -1을 출력하여라.

입력은 다음과 같은 형식으로 주어진다.

$T$ $\mathrm{case}_1$ $\mathrm{case}_2$

각 테스트 케이스마다 다다스가 추정한 단어를 한 줄에 출력한다. 후보 단어가 하나도 없다면 -1을 출력한다.

• $1 \leq T \leq 100\ 000$.
• $1 \leq N \leq 100\ 000$.
• 모든 테스트 케이스에 대한 $N$의 합은 이하이다.