Splitting Pairs

• 이것도 님게임 변형이라고 해야 할지 애매한데, 돌을 가져가는 것이 아니라 파일을 x개 제거한다. 그리고 남은 파일중 x개를 골라서 각각을 두 파일로 나눔으로써 파일의 갯수를 유지하는 규칙이다.
• 최종적인 패배포지션은 모든 파일에 돌이 1개씩만 있는 상태이다.
• 이제 상태를 나눠서 생각해보자. 모든 파일에 돌이 홀수개만 있는 포지션에서는, 이 중에서 x개 파일을 제거하고 남은 파일중 x개를 골라서 둘로 나누고 나면, 돌이 짝수개 있는 파일 x개가 남게 된다. 이 상태에서 상대방은 다시 돌이 홀수개 있는 파일 x개를 제거하고, 돌이 짝수개 있는 파일 x개를 각각 홀수/홀수로 쪼갤수 있다. 그러면 다시 모든 파일이 홀수인 포지션으로 돌아간다. 결국, 모든 파일이 홀수인 포지션에서는 어떤 행동을 취해도 다시 나한테 모든 파일이 홀수인 포지션이 돌아오고, 최종적으로는 모든 파일이 1인 포지션을 받게 되므로 패배하게 된다.
• 그러면 모든 파일을 홀수개로 만들수 있는 포지션은 모두 승리포지션인데, 나머지 모든 포지션이 여기에 해당하는 것은 아니다. 우선 제거할수 있는 파일 개수의 최댓값을 m이라고 하자. 짝수 파일이 m개 이하면, 홀수 파일 m개를 제거하고, 짝수파일들을 홀/홀로 나누어서 모두 홀수로 만들수 있다. 그리고 짝수파일이 2m개까지 늘어나도, 짝수파일 m개를 제거하고, 남은 m개의 짝수파일들을 홀/홀로 나누면 모두 홀수로 만들수 있다. 불가능한 경우는 딱 한가지인데, 총 파일 개수가 홀수개(=2m+1)이고 모든 파일이 짝수인 경우이다. 이때는 어떤행동을 취해도 짝수파일이 남게 된다. 짝수파일의 갯수를 2m 이하로 줄이면 상대방에게 승리포지션을 넘겨주는 것이므로 패배한다. 패배하지 않는 유일한 방법은 다시 모든 파일을 짝수개로 유지시킨채로 턴을 넘기는 것이다. 이것이 가능하기 위해서는 짝/짝으로 쪼갤수 있는 4의 배수개의 파일이 있어야만 가능하다. 그러면 다시.. 상대방에게 모든 파일이 2의 배수이지만 4의 배수는 아닌 포지션을 넘겨주면 이길수 있는데, 이것이 가능하려면 4의 배수가 2m개 이하여야 가능하다. 모든 파일을 홀수로 만들때와 동일한 전략이고, 비슷한 논의를 반복해서 하게 되면, 모든 파일의 갯수를 (2n-1)*(2^k) 로 {홀수}*{2의 거듭제곱}으로 표현했을때 k가 모두 같은값이면 패배, 그렇지 않으면 승리하게 된다.
• 요약하면..
  • n이 짝수일때 : 모든 파일이 홀수일때만 선공의 패배. 나머지는 선공 승리
  • n이 홀수일때 : 모든 파일이 같은 갯수의 2을 인수로 가지면 선공의 패배. 나머지는 선공 승리

"""Solution code for "BOJ 28155. Splitting Pairs".

- Problem link: https://www.acmicpc.net/problem/28155
- Solution link: http://www.teferi.net/ps/problems/boj/28155

Tags: [game theory]
"""

import sys


def main():
    t = int(sys.stdin.readline())
    for _ in range(t):
        n = int(sys.stdin.readline())  # pylint: disable=unused-variable
        s = [int(x) for x in sys.stdin.readline().split()]

        if n % 2 == 0:
            is_win_pos = any(x % 2 == 0 for x in s)
        else:
            is_win_pos = len({(x & -x) for x in s}) > 1

        print('1' if is_win_pos else '0')


if __name__ == '__main__':
    main()