SPOJ in Gyumri

  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