시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 1174 413 333 38.364%

문제

스파이들은 사령부와 통신하기 위해서 SMTP(비밀 메시지 전송 프로토콜)를 사용해 비밀 회선으로 전자 메시지를 보낸다. 메시지가 적들에 의해 조작되어 보내진 것이 아닌 진짜 메시지라는 것을 표시하기 위해 모든 메시지는 회선에 노이즈가 있었거나 발신 측에서 손을 떨면서 메시지를 보낸 것처럼 변형되는데, 이 변형 알고리즘은 메시지를 가로채는 자들이 우연히 변형 규칙을 흉내 낼 수 없을 정도로 정교하다. 또한 요원들의 머리에 총구가 겨눠져 강제로 메시지를 말한 경우 간단히 실수를 의도적으로 넣어 이 메시지가 강제로 쓰인 메시지라는 것을 알려줄 수 있다.

알고리즘대로 정확하게 변형된 메시지는 각 문자가 세 번 등장할 때 한 번 더 문자가 삽입된다. 예를 들면 요원이 "HELLOTHEREWELLBEFINE" 라는 메시지를 보내고 싶어 했다면 "HELLOTHEREEWELLLBEFINEE" 는 정확한 변형이다. 몇 년 동안 이 메시지들의 진짜 여부는 고도로 훈련된 원숭이들이 판별해내었다. 그러나 사령부에 도착하는 메시지들의 양이 많이 늘어나면서 이 작업을 자동으로 처리해주는 프로그램을 고안하기로 하였다.

입력

첫째 줄에 100 이하의 테스트 케이스의 개수가 주어진다. 그리고 각 테스트 케이스마다

  • 대문자로만 이루어진 10만자 이하의 문자열 M이 한 줄에 주어진다. 이 문자열은 검사해야할 메시지다.

출력

테스트 케이스마다

  • 메시지 M이 진짜 메시지면 “OK”를, 가짜 메시지면 “FAKE”를 한 줄에 출력한다.

예제 입력 1

3
BAPC
AABA
ABCABCBBAAACC

예제 출력 1

OK
FAKE
OK

힌트

W3sicHJvYmxlbV9pZCI6IjkzMjQiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM5YzRcdWM5ZGMgXHViYTU0XHVjMmRjXHVjOWMwIiwiZGVzY3JpcHRpb24iOiI8cD5cdWMyYTRcdWQzMGNcdWM3NzRcdWI0ZTRcdWM3NDAgXHVjMGFjXHViODM5XHViZDgwXHVjNjQwIFx1ZDFiNVx1YzJlMFx1ZDU1OFx1YWUzMCBcdWM3MDRcdWQ1NzRcdWMxMWMgU01UUChcdWJlNDRcdWJjMDAgXHViYTU0XHVjMmRjXHVjOWMwIFx1YzgwNFx1YzFhMSZuYnNwO1x1ZDUwNFx1Yjg1Y1x1ZDFhMFx1Y2Y1YylcdWI5N2MgXHVjMGFjXHVjNmE5XHVkNTc0IFx1YmU0NFx1YmMwMCBcdWQ2OGNcdWMxMjBcdWM3M2NcdWI4NWMgXHVjODA0XHVjNzkwIFx1YmE1NFx1YzJkY1x1YzljMFx1Yjk3YyBcdWJjZjRcdWIwYjhcdWIyZTQuIFx1YmE1NFx1YzJkY1x1YzljMFx1YWMwMCBcdWM4MDFcdWI0ZTRcdWM1ZDAgXHVjNzU4XHVkNTc0IFx1Yzg3MFx1Yzc5MVx1YjQxOFx1YzViNCZuYnNwO1x1YmNmNFx1YjBiNFx1YzljNCBcdWFjODNcdWM3NzQgXHVjNTQ0XHViMmNjIFx1YzljNFx1YzlkYyBcdWJhNTRcdWMyZGNcdWM5YzBcdWI3N2NcdWIyOTQgXHVhYzgzXHVjNzQ0IFx1ZDQ1Y1x1YzJkY1x1ZDU1OFx1YWUzMCBcdWM3MDRcdWQ1NzQgXHViYWE4XHViNGUwIFx1YmE1NFx1YzJkY1x1YzljMFx1YjI5NCBcdWQ2OGNcdWMxMjBcdWM1ZDAgXHViMTc4XHVjNzc0XHVjOTg4XHVhYzAwIFx1Yzc4OFx1YzVjOFx1YWM3MFx1YjA5OCBcdWJjMWNcdWMyZTAmbmJzcDtcdWNlMjFcdWM1ZDBcdWMxMWMgXHVjMTkwXHVjNzQ0IFx1YjVhOFx1YmE3NFx1YzExYyBcdWJhNTRcdWMyZGNcdWM5YzBcdWI5N2MgXHViY2Y0XHViMGI4Jm5ic3A7XHVhYzgzXHVjYzk4XHViN2ZjIFx1YmNjMFx1ZDYxNVx1YjQxOFx1YjI5NFx1YjM3MCwmbmJzcDtcdWM3NzQgXHViY2MwXHVkNjE1IFx1YzU0Y1x1YWNlMFx1YjlhY1x1Yzk5OFx1Yzc0MCBcdWJhNTRcdWMyZGNcdWM5YzBcdWI5N2MgXHVhYzAwXHViODVjXHVjYzQ0XHViMjk0IFx1Yzc5MFx1YjRlNFx1Yzc3NCBcdWM2YjBcdWM1ZjBcdWQ3ODgmbmJzcDtcdWJjYzBcdWQ2MTUmbmJzcDtcdWFkZGNcdWNlNTlcdWM3NDQmbmJzcDtcdWQ3NDlcdWIwYjQmbmJzcDtcdWIwYmMgXHVjMjE4IFx1YzVjNlx1Yzc0NCBcdWM4MTVcdWIzYzRcdWI4NWMgXHVjODE1XHVhZDUwXHVkNTU4XHViMmU0LiBcdWI2MTBcdWQ1NWMgXHVjNjk0XHVjNmQwXHViNGU0XHVjNzU4IFx1YmEzOFx1YjlhY1x1YzVkMCBcdWNkMWRcdWFkNmNcdWFjMDAgXHVhY2E4XHViMjIwXHVjODM4IFx1YWMxNVx1YzgxY1x1Yjg1YyBcdWJhNTRcdWMyZGNcdWM5YzBcdWI5N2MgXHViOWQwXHVkNTVjIFx1YWNiZFx1YzZiMCBcdWFjMDRcdWIyZThcdWQ3ODgmbmJzcDtcdWMyZTRcdWMyMThcdWI5N2MgXHVjNzU4XHViM2M0XHVjODAxXHVjNzNjXHViODVjIFx1YjEyM1x1YzViNCBcdWM3NzQgXHViYTU0XHVjMmRjXHVjOWMwXHVhYzAwIFx1YWMxNVx1YzgxY1x1Yjg1YyBcdWM0ZjBcdWM3NzggXHViYTU0XHVjMmRjXHVjOWMwXHViNzdjXHViMjk0IFx1YWM4M1x1Yzc0NCBcdWM1NGNcdWI4MjRcdWM5MDQgXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNTRjXHVhY2UwXHViOWFjXHVjOTk4XHViMzAwXHViODVjIFx1YzgxNVx1ZDY1NVx1ZDU1OFx1YWM4YyBcdWJjYzBcdWQ2MTVcdWI0MWMgXHViYTU0XHVjMmRjXHVjOWMwXHViMjk0IFx1YWMwMSBcdWJiMzhcdWM3OTBcdWFjMDAgXHVjMTM4IFx1YmM4OCZuYnNwO1x1YjRmMVx1YzdhNVx1ZDU2MCBcdWI1NGMgXHVkNTVjIFx1YmM4OCBcdWIzNTQgXHViYjM4XHVjNzkwXHVhYzAwIFx1YzBiZFx1Yzc4NVx1YjQxY1x1YjJlNC4gXHVjNjA4XHViOTdjIFx1YjRlNFx1YmE3NCBcdWM2OTRcdWM2ZDBcdWM3NzQgJnF1b3Q7PGNvZGU+SEVMTE9USEVSRVdFTExCRUZJTkU8XC9jb2RlPiZxdW90OyBcdWI3N2NcdWIyOTQgXHViYTU0XHVjMmRjXHVjOWMwXHViOTdjIFx1YmNmNFx1YjBiNFx1YWNlMCBcdWMyZjZcdWM1YjQmbmJzcDtcdWQ1ODhcdWIyZTRcdWJhNzQgJnF1b3Q7PGNvZGU+SEVMTE9USEVSRUVXRUxMTEJFRklORUU8XC9jb2RlPiZxdW90OyBcdWIyOTQgXHVjODE1XHVkNjU1XHVkNTVjIFx1YmNjMFx1ZDYxNVx1Yzc3NFx1YjJlNC4gXHViYTg3Jm5ic3A7XHViMTQ0IFx1YjNkOVx1YzU0OCBcdWM3NzQgXHViYTU0XHVjMmRjXHVjOWMwXHViNGU0XHVjNzU4IFx1YzljNFx1YzlkYyBcdWM1ZWNcdWJkODBcdWIyOTQgXHVhY2UwXHViM2M0XHViODVjIFx1ZDZjOFx1YjgyOFx1YjQxYyBcdWM2ZDBcdWMyMmRcdWM3NzRcdWI0ZTRcdWM3NzQgXHVkMzEwXHViY2M0XHVkNTc0XHViMGI0XHVjNWM4XHViMmU0LiBcdWFkZjhcdWI3ZWNcdWIwOTggXHVjMGFjXHViODM5XHViZDgwXHVjNWQwIFx1YjNjNFx1Y2MyOVx1ZDU1OFx1YjI5NCBcdWJhNTRcdWMyZGNcdWM5YzBcdWI0ZTRcdWM3NTggXHVjNTkxXHVjNzc0IFx1YjljZVx1Yzc3NCBcdWIyOThcdWM1YjRcdWIwOThcdWJhNzRcdWMxMWMgXHVjNzc0IFx1Yzc5MVx1YzVjNVx1Yzc0NCBcdWM3OTBcdWIzZDlcdWM3M2NcdWI4NWMgXHVjYzk4XHViOWFjXHVkNTc0XHVjOGZjXHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWFjZTBcdWM1NDhcdWQ1NThcdWFlMzBcdWI4NWMgXHVkNTU4XHVjNjAwXHViMmU0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCAxMDAgXHVjNzc0XHVkNTU4XHVjNzU4IFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVhYzFjXHVjMjE4XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhZGY4XHViOWFjXHVhY2UwIFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViOWM4XHViMmU0PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+XHViMzAwXHViYjM4XHVjNzkwXHViODVjXHViOWNjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzljNCAxMFx1YjljY1x1Yzc5MCBcdWM3NzRcdWQ1NThcdWM3NTggXHViYjM4XHVjNzkwXHVjNWY0IE1cdWM3NzQgXHVkNTVjIFx1YzkwNFx1YzVkMCZuYnNwO1x1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjNzc0IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc0MCBcdWFjODBcdWMwYWNcdWQ1NzRcdWM1N2NcdWQ1NjAgXHViYTU0XHVjMmRjXHVjOWMwXHViMmU0LjxcL2xpPlxyXG48XC91bD5cclxuIiwib3V0cHV0IjoiPHA+XHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjljOFx1YjJlNDxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPlx1YmE1NFx1YzJkY1x1YzljMCBNXHVjNzc0Jm5ic3A7XHVjOWM0XHVjOWRjIFx1YmE1NFx1YzJkY1x1YzljMFx1YmE3NCZuYnNwOyZsZHF1bzs8Y29kZT5PSzxcL2NvZGU+JnJkcXVvO1x1Yjk3YywgXHVhYzAwXHVjOWRjIFx1YmE1NFx1YzJkY1x1YzljMFx1YmE3NCZuYnNwOyZsZHF1bzs8Y29kZT5GQUtFPFwvY29kZT4mcmRxdW87XHViOTdjIFx1ZDU1YyBcdWM5MDRcdWM1ZDAmbmJzcDtcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiI5MzI0IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiR2VudWluZSBNZXNzYWdlcyIsImRlc2NyaXB0aW9uIjoiPHA+VG8gY29tbXVuaWNhdGUgd2l0aCBIUSwgc3BpZXMgc2VuZCBlbGVjdHJvbmljIG1lc3NhZ2VzIG92ZXIgdGhlIEluZm9ybWF0aW9uIFN1cGVyaGlnaHdheSB1c2luZyBhIHByb3RvY29sIGNhbGxlZCBTTVRQIChTZWNyZXQgTWVzc2FnZSBUcmFuc2xhdGlvbiBQcm90b2NvbCkuIFRvIGVuc3VyZSB0aGF0IHRoZXNlIG1lc3NhZ2VzIGFyZSBnZW51aW5lIGFuZCBoYXZlIG5vdCwgZm9yIGV4YW1wbGUsIGJlZW4gc2VudCBieSBhbiBldmlsIGFkdmVyc2FyeSwgZXZlcnkgbWVzc2FnZSAmbmJzcDtpcyBtb2RpXHVmYjAxZWQgaW4gc3VjaCBhIHdheSB0aGF0IGl0IGxvb2tzIGxpa2UgdGhlcmUgd2FzIG5vaXNlIG9uIHRoZSBjb21tdW5pY2F0aW9uIGxpbmUsIG9yIHRoZSBzZW5kZXIgd2FzIHZlcnkgbmVydm91cyB3aGlsZSB0eXBpbmcgdGhlIG1lc3NhZ2UuIEhvd2V2ZXIsIHRoZSBtdXRhdGlvbiBhbGdvcml0aG0gaXMgY2FyZWZ1bGx5IGNyYWZ0ZWQgc3VjaCB0aGF0IGFuIGltcG9zdGVyIGlzIHZlcnkgdW5saWtlbHkgdG8gcmVwbGljYXRlIHRoaXMgcGFydGljdWxhciBlZmZlY3QsIGFuZCBpdCBpcyBhbHNvIGVhc3kgZm9yIFx1ZmIwMWVsZCBhZ2VudHMgdG8gaW50ZW50aW9uYWxseSBpbnNlcnQgYSAmbGRxdW87bWlzdGFrZSZyZHF1bzsgaWYgdGhleSBhcmUgZm9yY2VkIGF0IGd1bnBvaW50IHRvIHdyaXRlIGEgbWVzc2FnZS48XC9wPlxyXG5cclxuPHA+SW4gYSBjb3JyZWN0bHkgbXV0YXRlZCBtZXNzYWdlIGV2ZXJ5IHRoaXJkIGFwcGVhcmFuY2Ugb2YgZWFjaCBsZXR0ZXIgaXMgZHVwbGljYXRlZC4gRm9yIGV4YW1wbGUsICZsZHF1bzs8Y29kZT5IRUxMT1RIRVJFRVdFTExMQkVGSU5FRTxcL2NvZGU+JnJkcXVvOyBpcyB0aGUgY29ycmVjdCBtdXRhdGlvbiBpZiB0aGUgYWdlbnQgd2FudGVkIHRvIHNlbmQgJmxkcXVvOzxjb2RlPkhFTExPVEhFUkVXRUxMQkVGSU5FPFwvY29kZT4mcmRxdW87LiBGb3IgdGhlIHBhc3QgZmV3IGRlY2FkZXMgdGhlc2UgbWVzc2FnZXMgaGF2ZSBiZWVuIGNoZWNrZWQgYnkgaGlnaGx5IHRyYWluZWQgbW9ua2V5cy4gU2luY2UgdGhlIG51bWJlciBvZiBtZXNzYWdlcyBhcnJpdmluZyBhdCB0aGUgSFEgaGFzIGdyZWF0bHkgaW5jcmVhc2VkIHJlY2VudGx5LCB0aGV5IGhhdmUgdGFza2VkIHlvdSB3aXRoIHdyaXRpbmcgYW4gYXV0b21hdGVkIHByb2dyYW0gdGhhdCBjYW4gYWxlcnQgSFEgd2hlbiBhIG1lc3NhZ2UgaXMgZGVcdWZiMDFuaXRlbHkgZmFrZSBhbmQgbm90IHNlbnQgYnkgb3VyIGFnZW50LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+T24gdGhlIFx1ZmIwMXJzdCBsaW5lIG9uZSBwb3NpdGl2ZSBudW1iZXI6IHRoZSBudW1iZXIgb2YgdGVzdCBjYXNlcywgYXQgbW9zdCAxMDAuIEFmdGVyIHRoYXQgcGVyIHRlc3QgY2FzZTo8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5vbmUgbGluZSB3aXRoIGEgc3RyaW5nIE0gKDEgJmxlOyBsZW5ndGgoTSkgJmxlOyAxMDAgMDAwKSwgY29uc2lzdGluZyBvZiB1cHBlcmNhc2UgbGV0dGVycyBvbmx5OiB0aGUgaW5jb21pbmcgbWVzc2FnZSB0byBjaGVjay48XC9saT5cclxuPFwvdWw+XHJcbiIsIm91dHB1dCI6IjxwPlBlciB0ZXN0IGNhc2U6PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+b25lIGxpbmUgd2l0aCBlaXRoZXIgJmxkcXVvOzxjb2RlPk9LPFwvY29kZT4mcmRxdW87IG9yICZsZHF1bzs8Y29kZT5GQUtFPFwvY29kZT4mcmRxdW87LCBpbmRpY2F0aW5nIHdoZXRoZXIgb3Igbm90IHRoZSBtZXNzYWdlIE0gY2FuIGJlIHRoZSByZXN1bHQgb2YgYSBjb3JyZWN0bHkgYXBwbGllZCBtdXRhdGlvbiB0byBzb21lICh1bnNwZWNpXHVmYjAxZWQpIG9yaWdpbmFsIG1lc3NhZ2UuPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=