문제 태그

• 게임 이론
• 정렬
• 상태 압축

한국어 문제 해석

칠판에 N개의 0 이상의 정수 $A_1, A_2, ..., A_N$이 적혀 있다.

Alice와 Bob이 게임을 한다. Alice부터 시작해서 두 사람은 번갈아 다음 조작을 수행하며, 칠판에 적힌 정수의 개수를 0개로 만든 사람이 이긴다.

현재 칠판에 적힌 0 이상의 정수 중 최솟값을 m이라고 하자.

• m이 0보다 크다면, 1 이상 m 이하인 양의 정수 x를 하나 고른다. 그리고 칠판에 적힌 모든 정수를 현재 값에서 x를 뺀 값으로 바꾼다.
• m이 0이라면, 칠판에 적힌 0 중 하나 이상을 지운다.

두 사람이 모두 이기기 위해 최적으로 행동한다고 할 때 누가 이기는지 판정한다.

T개의 테스트 케이스가 주어지므로, 각각에 대해 답을 구한다.

제약

• T는 1 이상 200000 이하이다.
• 각 테스트 케이스에서 N은 1 이상 200000 이하이다.
• 모든 i에 대해 $A_i$는 0 이상 1000000000 이하이다.
• 모든 테스트 케이스에 대한 N의 합은 200000 이하이다.
• 입력으로 주어지는 값은 모두 정수다.

입력