Թաքցված խնդիր
|Այս խնդիրը թաքցված է խմբագրական խրհրդի անդամի կողմից քանի որ կամ այն ոչ ճիշտ լեզվով է գրված,|կամ թեստային տվյալներն են սխալ, կամ խնդրի ձևակերպումը պարզ չէ։|

ACM_0037 - GENUINE MESSAGES

  To communicate with HQ, spies send electronic messages over the Information Superhigh- way using a protocol called SMTP (Secret Message Translation Protocol). To ensure that these messages are genuine and have not, for example, been sent by an evil adversary, every mes- sage is modified in such a way that it looks like there was noise on the communication line, or the sender was very nervous while typing the message. However, the mutation algorithm is carefully crafted such that an imposter is very unlikely to replicate this particular effect, and it is also easy for field agents to intentionally insert a “mistake” if they are forced at gunpoint to write a message.

   In a correctly mutated message every third appearance of each letter is duplicated. For example, “HELLOTHEREEWELLLBEFINEE” is the correct mutation if the agent wanted to send “HELLOTHEREWELLBEFINE”. For the past few decades these messages have been checked by highly trained monkeys. Since the number of messages arriving at the HQ has greatly increased recently, they have tasked you with writing an automated program that can alert HQ when a message is definitely fake and not sent by our agent.

Input

   On the first line one positive number: the number of test cases, at most 100. After that per test case:

  • one line with a string M (1 length(M ) 100 000), consisting of uppercase letters only: the incoming message to check.

Output

   Per test case:

  • one line with either “OK” or “FAKE”, indicating whether or not the message M can be the result of a correctly applied mutation to some (unspecified) original message. 

Examples

 

stdin

stdout

1

3

BAPC

AABA

ABCABCBBAAACC

OK

FAKE

OK


Ավելացրեց.Հրանտ Հովհաննիսյան
Ամսաթիվ.2013-12-21
Ժամանակի սահմանափակումը.1s
Ծրագրի տեքստի սահմանափակումը.50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Լեզուներ.Բոլորը բացի ASM32 ASM64 GAWK CLPS CLOJURE D ERL FSHARP FORTRAN GOSU HASK ICON ICK NEM NIM OBJC-CLANG PICO PIKE PYPY PY_NBC RUST SCM guile CHICKEN SED TCL WHITESPACE
Աղբյուրը.Benelux Preliminary (BAPC) 2013.G

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.