돌 더미 쪼개기

앨리스와 밥이 변형된 님 게임을 한다. 처음에 빈 더미가 아닌 돌 더미 여러 개가 앞에 놓여 있다. 두 사람은 번갈아 차례를 진행하며, 앨리스가 먼저 시작한다.

한 턴에 플레이어는 다음 동작을 순서대로 반드시 수행해야 한다.

• 돌 더미를 일부 제거한다. 제거하는 더미 수는 최소 1개이고, 전체 더미 수의 절반을 넘을 수 없다.
• 남은 더미 중 제거한 것과 같은 수의 더미를 고르고, 고른 더미 각각을 빈 더미가 아닌 두 더미로 나눈다.

유효한 턴이 끝나면 빈 더미가 아닌 더미의 수는 게임 시작 때와 같아야 한다. 턴에서 모든 동작을 수행하지 못하는 플레이어는 진다.

여러 게임이 주어지며, 각 게임에서 두 플레이어가 최적으로 플레이할 때 누가 이기는지 구한다.

첫 줄에 게임 수를 나타내는 정수 $t$ ($1 \leq t \leq 1\,000$)가 주어진다. 각 게임은 두 줄로 주어진다. 게임의 첫 줄에는 돌 더미의 개수 $n$ ($2 \leq n \leq 50$)이 주어진다. 다음 줄에는 각 더미의 돌 개수 $s$ ($1 \leq s \leq 10^{12}$) $n$개가 공백으로 구분되어 주어진다.

$t$줄을 출력한다. 각 게임에 대해 앨리스가 이기면 $1$, 밥이 이기면 $0$을 출력한다. 결과는 입력에 나온 순서대로 출력한다.