거짓 지능

인공지능이 세상을 차지하고 있다. 적어도 곧 그럴 계획이다. 기계는 모든 게임에서 이기고, 모든 질문에 답하고, 사람을 대신해 모든 결정을 내릴 만큼 똑똑해진다. 이런 이야기가 무섭게 들려서, 기계에 사람다운 구석을 조금 넣자는 제안이 나왔다. 기계가 가끔 답을 모르는 척하고 대신 불확실하다고 말하게 하는 것이다.

물론 기계는 속으로 여전히 정확한 규칙을 따른다. 세 값 논리의 규칙이다. 이 논리는 불 논리의 두 값 F(거짓)와 T(참)에 세 번째 값 U(불확실)를 더하고, 논리 연산자를 아래 표처럼 확장한다. 각 표에서 행은 첫 번째 인자를, 열은 두 번째 인자를 고르고, 둘 다 F, U, T 순서로 놓인다.

예를 들어 불 논리와 마찬가지로 F ∨ T = T이고, T ∧ U = U이며, F → U = T이다.

앞의 세 연산자만으로는 모든 함수를 만들지 못한다. $x$, $y$와 AND, OR, IMPLIES로 쓸 수 있는 함수는 $x = y =$ U에서 값이 U가 된다. 그래서 그중 어느 것도 항상 T인 상수 함수가 아니다. 네 번째 표의 연산자 EQUALS는 두 인자가 같으면 T를, 다르면 F를 돌려준다. EQUALS를 더 쓰더라도 $x$, $y$와 AND, OR, IMPLIES, EQUALS로 쓴 식 중에 항상 F인 상수 함수는 없다.

표로 주어진 함수 $g(x, y)$가 $x$, $y$와 AND, OR, IMPLIES, EQUALS로 표현되는지 판정하라. 기계가 자기 한계를 알아야 하기 때문이다.

첫째 줄에 판정할 함수의 개수 $n$ (1 ≤ $n$ ≤ 20000)이 주어진다. 이어서 $n$개의 함수 설명이 주어진다.

함수 설명 하나는 네 줄이다. 그중 첫 줄은 빈 줄이다. 남은 세 줄은 함수 $g$의 값 $g(x, y)$를 표로 적은 것이다. 표는 3행 3열이고, 행은 $x$의 값을, 열은 $y$의 값을 각각 F, U, T 순서로 나타내며, 배치는 위의 표와 같다. 이 세 줄은 각각 공백 하나로 구분한 값 세 개로 이루어지고, 각 값은 F, U, T 중 하나다.

각 함수 설명마다 입력과 같은 순서로 한 줄씩 출력한다. 주어진 함수 $g(x, y)$를 $x$, $y$와 AND, OR, IMPLIES, EQUALS로 표현할 수 있으면 definable을 출력하고, 표현할 수 없으면 undefinable을 출력한다.