Communication Channels

Classical information theory rests on the idea of a communication channel. Claude Shannon founded it in his 1948 paper "A Mathematical Theory of Communication", and its central problem is the engineering problem of sending information over a noisy channel.

This problem deals with the simplest noisy channel, the binary symmetric channel (BSC). A BSC transmits a sequence of bits, and each transmitted bit is flipped to the wrong bit with probability $p$. That $p$ is called the crossover probability. Bits flip independently of each other, so a communication of length $l$ arrives correctly with probability $(1-p)^l$. A channel with $p = 1/2$ is useless, and a channel with $p > 1/2$ turns into a channel with crossover probability $1-p$ by flipping every bit of the output, so you may always assume $p < 1/2$.

Communication over a noisy channel is still possible. You are doing it right now. To make it work, the sender adds extra bits so the receiver can detect or even correct errors. Parity bits, cyclic redundancy checks (CRC) and Golay codes do that. This problem does not use any such code.

You are given transmission records that passed through a binary symmetric channel. Decide for each transmission whether it arrived correctly.

The first line contains the number of transmissions $T$. Each of the next $T$ lines contains the input and the output of one transmission as two binary strings separated by a single space.

• $0 < T \le 100$
• Every input and output has length less than $120$.
• The input and the output of one transmission have the same length. The channel only flips bits, it never inserts or drops a bit.
• $T$ is written in decimal.

For each transmission print one line: OK if the communication was transmitted correctly, ERROR if it was not.