eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Оригинальные сообщения

Оригинальные сообщения

Лимит времени 1 секунда
Лимит использования памяти 64 MiB

Для связи со штаб-квартирой шпионы отправляют электронные сообщения по информационной магистрали, используя протокол под названием СППС (Секретный Протокол Передачи Сообщений). Чтобы убедиться, что эти сообщения являются подлинными, а не например отправлены злейшим врагом, каждое сообщение модифицируется таким образом, что оно выглядит как будто присутствовал шум на линии связи, или как будто отправитель очень нервничал во время набора текста сообщения. Однако алгоритм мутации является достаточно искусным, так что самозванец с очень малой вероятностью сможет повторить этот эффект, а местным агентам достаточно легко преднамеренно вставить "ошибку", если они вдруг вынуждены писать сообщение под дулом пистолета.

В корректно мутированном сообщении каждое третье появление каждой буквы дублируется. Например, "HELLOTHEREEWELLLBEFINEE" - корректное преобразование сообщения "HELLOTHEREWELLBEFINE", которое послал агент. За последние несколько десятилетий эти сообщения были проверены высококвалифицированными обезьянами. Так как количество поступающих в штаб-квартиру сообщений значительно выросло в последнее время, то Вам поручили написать автоматизированную программу, которая сможет предупредить штаб о поступлении подделанного сообщения - то есть такого, которое прислано не нашим агентом.

Входные данные

Первая строка содержит количество тестов, не большее 100. Каждый тест состоит из одной строки M (1 length(M) 100000), содержащей только буквы верхнего регистра: входное сообщение, которое следует проверить.

Выходные данные

Для каждого теста вывести в отдельной строке "OK" или "FAKE" в зависимости от того, является ли сообщение M корректной мутацией некоторого (неизвестного) исходного сообщения.

Пример

Входные данные #1
3
BAPC
AABA
ABCABCBBAAACC
Выходные данные #1
OK
FAKE
OK
Источник 2013 Benelux Algorithm Programming Contest (BAPC), Preliminaries, Сентябрь 28, Задача G