오류 검출

치열한 전투 도중, 토니 스타크의 슈트는 기술 데이터를 주고받기 위해 자비스(JARVIS)와 끊임없이 통신한다. 전송되는 각 데이터는 16비트 정수 값의 형태를 띤다. 그런데 (토르가 사방에 뿌려대는 번개처럼) 여러 대기 교란 때문에 데이터가 손상될 위험이 있다.

이러한 손상을 검출하기 위해, 전송되는 16비트 값마다 추가 비트 하나를 함께 보낸다. 검사 비트(check bit) 라고 부르는 이 추가 비트의 값은 다음과 같다.

• 해당 16비트 정수를 2진수로 나타냈을 때 1의 개수가 홀수이면 1,
• 1의 개수가 짝수이면 0.

그 결과, 17비트 전체에서 값이 1인 비트의 개수는 항상 짝수가 된다.

예를 들어 정수 $45$는 2진수로 $0000000000101101$이며 1의 개수가 짝수이므로 검사 비트는 $0$이다. 정수 $34173$은 2진수로 $1000010101111101$이며 1의 개수가 홀수이므로 검사 비트는 $1$이다.

첫째 줄에 테스트 케이스의 수 $T$가 주어진다 ($T < 100$).

이후 $T$개의 각 줄에는 하나의 테스트 케이스가 주어진다. 각 줄에는 16비트 정수($0$부터 $65535$까지)와 그 검사 비트($0$ 또는 $1$)가 차례로 주어진다.

각 테스트 케이스마다, 검사 비트가 그 정수의 1의 개수(짝수/홀수)와 일치하지 않으면 Corrupt를, 일치하면 Valid를 출력한다. 각 답은 한 줄에 하나씩 출력한다.