비밀번호

숄더 서핑(shoulder surfing)은 노트북이나 휴대폰처럼 다른 사람이 쓰는 기기의 화면을 몰래 훔쳐보아 정보를 알아내는 행위이다. 모바일 기기가 널리 쓰이면서 이런 식으로 개인정보가 새어 나갈 위험도 커지고 있다.

비밀번호를 훔쳐보기 어렵게 만들기 위해, 화면 키패드를 $6 \times 5$ 격자로 보여 준다고 하자. 5개의 각 열은 독립적으로 돌릴 수 있는 바퀴(휠)의 보이는 부분이고, 모든 휠에는 알파벳 대문자 26자가 들어 있다. 열마다 휠을 따로 돌릴 수 있으므로, 어떤 글자든 원하는 열에 나타나게 할 수 있다.

그림 1. 비밀번호를 담은 $6 \times 5$ 격자의 한 가지 모습.

비밀번호는 길이가 5인 문자열 $p_1 p_2 p_3 p_4 p_5$ 이다. 모든 위치 $i$ 에 대해 글자 $p_i$ 가 격자의 $i$ 번째 열 어딘가에 나타나면, 그 격자는 해당 비밀번호를 통과시킨다. 각 글자가 몇 번째 행에 있는지는 중요하지 않고, 올바른 열에 들어 있기만 하면 된다.

예를 들어 비밀번호가 COMPU 라면, C 가 1열, O 가 2열, M 이 3열, P 가 4열, U 가 5열에 나타나는 그림 2의 격자는 이 비밀번호를 통과시킨다.

그림 2. 비밀번호 COMPU 를 통과시키는 격자.

열에 글자가 있는지만 따지므로 같은 비밀번호를 통과시키는 격자는 아주 많고, 시도할 때마다 그리고 열마다 휠의 글자 배열이 새로 섞인다. $6 \times 5$ 격자 하나로는 최대 $6^5 = 7776$ 개의 후보 비밀번호가 가능하므로, 격자를 한 번 본 사람은 그중 어느 것이 진짜 비밀번호인지 알 수 없다.

하지만 약점이 있다. 같은 사람에게서 서로 다른 두 격자를 관찰하면 후보의 범위가 두 격자 모두와 맞는 비밀번호로 좁혀져 진짜 비밀번호가 드러날 수 있다. 예를 들어 진짜 비밀번호가 COMPU 일 때, 두 번째로 관찰한 격자에 따라 DPMAG 도 후보가 될 수 있다.

그림 3. COMPU 와 DPMAG 는 모두 두 격자와 맞는 후보이다.

관찰자가 포착한 두 개의 격자가 주어진다. 비밀번호 $p_1 p_2 p_3 p_4 p_5$ 가 후보가 되려면, 모든 열 $i$ 에 대해 글자 $p_i$ 가 첫 번째 격자의 $i$ 번째 열과 두 번째 격자의 $i$ 번째 열에 모두 나타나야 한다. 모든 후보 비밀번호를 사전순으로 나열했을 때 $K$ 번째 비밀번호를 구하라.

아래 첫 번째 예제의 두 격자에서, 사전순으로 앞의 다섯 후보는 ABGAG, ABGAS, ABGAU, ABGPG, ABGPS 이다.

$K$ 가 전체 후보 개수보다 크면 NO 를 출력한다.

첫째 줄에 테스트 케이스 수 $T$ 가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫 줄에 찾을 비밀번호의 순위를 나타내는 정수 $K$ ($1 \le K \le 7777$) 가 있다. 이어지는 6줄은 첫 번째 격자의 6개 행이고, 그다음 6줄은 두 번째 격자의 6개 행이다. 격자의 각 행은 대문자 5글자로 이루어진다.

각 테스트 케이스마다 한 줄에 사전순으로 $K$ 번째 후보 비밀번호를 출력한다. 후보가 $K$ 개보다 적으면 NO 를 출력한다.