문제

격렬한 싸움 중 지속적으로 토니 스타크의 슈트는 JARVIS와 기술 관련 데이터를 공유합니다. 이 정보는 16-비트 정수 값으로 전달됩니다. 하지만 (토르가 번개를 주변에 생성하는 등) 여러 환경적 조건 때문에 데이터가 손상될 위험이 있습니다. 이러한 손상을 탐지하기 위해, 16비트 정수 값을 전송할 때 추가로 하나의 비트를 전송합니다. 추가되는 이 하나의 비트는 검사 비트라 불리며, 16비트 정수가 이진수 표기 시 홀수 개의 1을 가지고 있을 때 1입니다. 해당하는 16비트 정수가 이진수 표기 시 짝수 개의 1을 가지고 있다면 검사 비트는 0입니다. 그 효과는 아래와 같습니다: 총 17비트에서 비트 값이 1인 비트 수는 언제나 짝수입니다.

예를 들어, 45는 이진수로 표기 시 0000000000101101이며 짝수 개의 1을 가지고 있으므로 검사 비트는 0이 됩니다. 정수 34173은 이진수 표기로 1000010101111101이므로 홀수 개의 1을 가지고 있기 때문에 검사 비트는 1입니다.

입력

첫 줄에 테스트 케이스의 수 (< 100)가 주어집니다. 이후, 각 줄이 하나의 테스트 케이스를 나타냅니다: 첫 번째 숫자는 (int로 제공되는) 16비트 정수이며, 다음 수는 (역시 int로 제공되는) 검사 비트입니다.

출력

각 테스트 케이스에 대해 검사 비트가 정수의 1의 개수가 짝수인지 홀수인지 여부와 맞지 않는다면 "Corrupt"를, 맞는다면 "Valid"를 출력합니다.