진짜 메시지

스파이는 사령부와 연락할 때 비밀 메시지 전송 프로토콜(SMTP)로 비밀 회선에 전자 메시지를 흘려보낸다. 적이 가로채서 조작한 것이 아니라 요원이 직접 보낸 진짜 메시지임을 알리려고, 모든 메시지는 회선에 잡음이 섞였거나 발신자가 손을 떨며 입력한 것처럼 보이도록 변형해서 내보낸다. 변형 규칙은 아주 정교해서 메시지를 가로챈 쪽이 우연히 흉내 낼 수 없다. 요원이 총구 앞에서 메시지를 강제로 불러야 하는 상황이라면, 변형에 일부러 실수를 넣어 이 메시지가 강제로 쓰였다는 사실을 알릴 수 있다.

변형 규칙은 이렇다. 원본 메시지를 앞에서부터 한 글자씩 그대로 옮겨 적되, 어떤 문자를 3번째, 6번째, 9번째처럼 3의 배수 번째로 적는 순간 그 문자를 바로 뒤에 한 번 더 적는다. 이렇게 덧붙인 글자는 등장 횟수로 세지 않는다.

예를 들어 원본이 HELLOTHEREWELLBEFINE이면 E를 3번째로 적을 때와 6번째로 적을 때, 그리고 L을 3번째로 적을 때 같은 글자를 하나씩 덧붙이므로 정확한 변형은 HELLOTHEREEWELLLBEFINEE이다.

지금까지는 훈련받은 원숭이가 메시지의 진짜 여부를 가려냈다. 사령부에 도착하는 메시지가 크게 늘면서 이 판별을 자동으로 처리하는 프로그램이 필요해졌다. 메시지 M이 주어질 때, 규칙대로 변형하면 정확히 M이 되는 원본 메시지가 존재하는지 판정하라.

첫째 줄에 테스트 케이스의 개수 T가 주어진다. T는 100 이하이다.

이어서 테스트 케이스마다 한 줄에 검사할 메시지 M이 주어진다. M은 대문자 알파벳으로만 이루어지고, 길이는 100,000 이하이다.

테스트 케이스마다 한 줄에 답을 출력한다. 메시지 M이 규칙대로 변형한 진짜 메시지면 OK를, 아니면 FAKE를 출력한다.