Error Detection

In the middle of a fierce battle, Tony Stark's suit constantly exchanges technical data with JARVIS. Each piece of data is transmitted as a 16-bit integer value. Because of various atmospheric disturbances (for instance, all the lightning Thor throws around), transmitted data can be corrupted.

To help detect corruption, one extra bit is sent alongside every 16-bit value. This extra bit, called the check bit, is:

• 1 if the corresponding 16-bit integer has an odd number of 1s when written in binary;
• 0 if it has an even number of 1s when written in binary.

As a result, the number of 1-bits across the combined 17 bits is always even.

For example, the integer $45$ is $0000000000101101$ in binary, which has an even number of 1s, so its check bit is $0$. The integer $34173$ is $1000010101111101$ in binary, which has an odd number of 1s, so its check bit is $1$.

The first line contains the number of test cases $T$ ($T < 100$).

Each of the next $T$ lines contains one test case: a 16-bit integer (from $0$ to $65535$) followed by its check bit ($0$ or $1$).

For each test case, print Corrupt if the check bit does not match the parity (the even/odd count of 1s) of the integer, or Valid if it does. Print each answer on its own line.