추측 게임 II

어떤 문의 비밀번호는 네 자리 코드이며, 앞을 0으로 채워 항상 정확히 네 자리로 표기한다 (0000부터 9999까지).

누군가 이 코드를 계속 추측했다. 각 추측도 네 자리 코드이고, 문은 두 개의 수로 답한다.

• 원(circle) — 추측한 자리의 숫자가 같은 위치의 비밀 숫자와 일치하는 위치의 개수;
• 사각형(square) — 그 외의 추측 숫자 중 비밀번호에 존재하지만 다른 위치에 있는 것의 개수를 중복까지 고려해 센 값. 형식적으로, 각 숫자 값 $d$에 대해 $m_d = \min(\text{추측에서 }d\text{의 개수},\ \text{비밀번호에서 }d\text{의 개수})$라 하면 $\text{원} + \text{사각형} = \sum_d m_d$이다.

하나의 비밀번호에 대해 최대 8개의 (추측, 응답) 쌍이 기록되어 있다. 오직 이 쌍들만으로 다음 중 어느 경우인지 판단하라.

1. 기록된 쌍만으로 비밀번호가 유일하게 결정된다.
2. 아직 유일하지 않지만, 남은 모든 후보를 서로 구별해 줄 수 있는 추측이 하나 존재한다.
3. 한 번 더 추측하더라도 비밀번호를 항상 알아낼 수는 없다.

어떤 추측이 비밀번호를 유일하게 식별한다는 것은, 기록된 쌍들과 여전히 모순되지 않는 모든 코드에 대해 그 추측이 서로 다른 응답을 만들어 낸다는 뜻이다. 그러면 문이 어떤 응답을 주더라도 남는 후보는 정확히 하나가 된다.

예를 들어 기록된 쌍이 5888 → 원 3, 사각형 0, 1234 → 원 0, 사각형 0, 4567 → 원 0, 사각형 0이라 하자. 이와 모순되지 않는 코드는 0888, 8888, 9888 셋뿐이다. 다음으로 0009를 추측하면 이 셋의 응답이 각각 원 1, 원 0, 원 0·사각형 1로 모두 달라져 비밀번호가 식별된다. 반면 0888을 추측하면 8888과 9888이 모두 원 3·사각형 0으로 답하므로 구별되지 않는다. 이 경우 유효한 추측이 여럿이며(0009, 0889, 0898, …), 그중 수치적으로 가장 작은 0009를 출력한다.

첫 줄에 테스트 케이스의 수 $T$가 주어진다 ($T \le 1000$).

이어지는 $T$개의 줄은 각각 하나의 테스트 케이스를 나타낸다. 각 줄은 기록된 (추측, 응답) 쌍의 개수 $n$ ($0 < n \le 8$)으로 시작하고, 그 뒤에 $3n$개의 정수가 온다. 세 정수씩 묶인 각 그룹은 추측, 원, 사각형의 삼중쌍이다.

각 추측은 정수로 주어지며, 왼쪽을 0으로 채워 네 자리로 해석한다. 예를 들어 추측 1은 0001을 뜻한다. 한 줄의 토큰들은 임의의 공백으로 구분될 수 있다.

각 테스트 케이스마다 정확히 한 줄을 출력한다.

• 기록된 쌍만으로 비밀번호가 이미 결정되면 The secret is: SSSS를 출력한다. 여기서 SSSS는 네 자리로 나타낸 비밀번호이다.
• 그렇지 않고 어떤 추가 추측이 비밀번호를 유일하게 식별할 수 있으면 There is a guess that can uniquely identify the secret: GGGG를 출력한다. GGGG는 네 자리로 나타낸 그 추측이며, 여러 개가 가능하면 수치적으로 가장 작은 것을 사용한다.
• 그 외의 경우 There is no guess that can uniquely identify the secret.를 출력한다.