그리드 님

아웃랜드에 숨어 지내던 샘과 쿼라는 심심해져서 그리드 님(grid nim) 이라는 게임을 시작한다. 이는 고전 게임 님(nim) 을 복잡하게 변형한 것이다. 게임판은 한 줄로 늘어선 $n$ 개의 무더기로 이루어지며, 각 무더기에는 똑같은 동전이 몇 개씩 들어 있다(그림 참고). 두 사람은 번갈아 수를 둔다.

한 번의 수에서 플레이어는 줄의 왼쪽 끝 또는 오른쪽 끝 에 있는 무더기 하나를 골라 제거한다. 여기에 한 가지 규칙이 더 있다: 한 플레이어는 자신의 연속된 세 번의 차례에서 서로 이웃한 무더기 세 개를 연달아 가져갈 수 없다. (게임이 끝나갈 무렵 무더기가 하나만 남았을 때에는 이 규칙이 적용되지 않는다.) 판이 비면 게임이 끝난다.

먼저 두는 플레이어는 자신이 모은 동전 수가 나중에 두는 플레이어가 모은 동전 수 이상 이면 이기고, 그렇지 않으면 나중에 두는 플레이어가 이긴다.

샘이 먼저 둔다고 할 때, 그림의 판에서 게임이 진행될 수 있는 한 가지 예는 다음과 같다.

• 샘이 왼쪽 끝에서 무더기 1을 가져간다 (동전 7개)
• 쿼라가 오른쪽 끝에서 무더기 5를 가져간다 (동전 5개)
• 샘이 오른쪽 끝에서 무더기 4를 가져간다 (동전 3개)
• 쿼라가 오른쪽 끝에서 무더기 3을 가져간다 (동전 4개)
• 샘이 무더기 2를 가져간다 (동전 0개)

마지막에 샘은 $7 + 3 = 10$ 개의 동전을 가져 쿼라보다 많으므로 샘이 이긴다. 사실 쿼라가 어떻게 하든 샘이 이긴다. 쿼라가 대신 무더기 2(동전 0개)를 가져가면, 샘은 동전 5개짜리 무더기를 가져가 15개 또는 16개로 더 높은 합계를 만들 수 있다.

이 예에서는 특수 규칙이 문제가 되지 않는다. 대신 무더기가 아주 많은 판에서 다음과 같이 시작하는 경우를 생각해 보자.

샘 - 왼쪽, 쿼라 - 오른쪽, 샘 - 왼쪽, 쿼라 - 오른쪽

다음 차례에 샘은 다시 왼쪽 끝에서 가져갈 수 없다. 그러면 이웃한 세 번째 무더기가 되기 때문이며, 따라서 오른쪽 끝에서 가져가야 한다.

샘 - 왼쪽, 쿼라 - 오른쪽, 샘 - 왼쪽, 쿼라 - 오른쪽, 샘 - 오른쪽

이제 쿼라가 마지막 두 차례에 오른쪽 끝에서 가져갔더라도, 그녀는 여전히 어느 쪽 끝에서든 가져갈 수 있다. 방금 샘이 오른쪽 끝에서 가져갔기 때문에, 쿼라가 오른쪽에서 가져가더라도 그녀에게는 이웃한 세 번째 무더기가 아니므로 허용된다.

쿼라는 완벽하게 플레이하며 항상 최선의 수를 둔다. 공평하게 하려고 그녀는 샘에게 먼저 두게 한다. 당신의 임무는 샘을 돕는 것이다. 시작 판이 주어질 때, 쿼라가 항상 최적으로 둔다고 가정하고 먼저 두는 샘에게 이기는 전략이 있는지 판단하라.

첫째 줄에 테스트 케이스의 수 $T$ 가 주어진다($T \le 50$). 이어지는 각 줄은 하나의 테스트 케이스를 나타낸다. 각 줄은 무더기의 개수 $k$ 로 시작하고, 그 뒤에 왼쪽부터 오른쪽 순서로 각 무더기의 동전 개수를 나타내는 정수 $k$ 개가 온다. 모든 동전 개수는 $0$ 이상이고 $2^{30}$ 미만이다.

각 테스트 케이스마다, 먼저 두는 샘에게 이기는 전략이 있으면 YES 를, 없으면 NO 를 한 줄에 하나씩 출력하라.