Elves from the Lothvain forest have created a very interesting game. The rules are very simple:

• There are two players.

• In the beginning there are n groups of stones. The i-th group contains a_i stones.

• A player has to take a positive number of stones from exactly one of the groups in his turn.

• A player who can‘t make a move (each group is empty) wins.

Very soon they have learnt how to always make the best possible move. Your task is to write a program that computes which of the players has a winning strategy for a given situation.

INPUT

The first number appearing in the input is number of datasets t (5<=t<=50). Each dataset is given in following format. The first row contains a single number n (1<=n<=10000). The next row contains exactly n numbers: a_1, a_2,..., a_n (0<=a_i<=1000000000). There are no empty lines between the datasets. You may assume that at least one group of stones is not empty.

OUTPUT

For each of datasets your program should write:

• 1 if the first player has a winning strategy

• 2 otherwise

in a separate row.

SAMPLE

INPUT
 
2
3
1 1 1
5
1 0 1 1 1
 
OUTPUT
2
1

题意：NIM游戏的变种，胜利状态变为不能取的取胜。

先手必胜当且仅当：

1、若所有堆的石子最大数量为1，且数量为1的堆数为偶数

2、若有的堆数量超过1，SG为非0

证明：情况一、很容易想到。

情况二、先分析只有一堆石子的数量大于1，那么这个人可以控制后手的1的数量，因此是必胜态（SG必为非0）。

其次，如果有大于1堆的石子的数量大于2，那么如果SG为非0，那么先手只要将SG变为0，后手无论进行什么操作，SG都会变成非0（异或的性质），这样进行下去，终会达到必胜态（只有一堆石子的最大数量大于1）。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
using namespace std;
int main(){

    int ncase;
    cin >> ncase;
    while(ncase--){
        int n;
        int ans = 0;
        scanf("%d",&n);
        int cnt = 0;
        for(int i = 0; i < n; i++){
            int t;
            scanf("%d",&t);
            if(t>1) cnt++;
            ans ^= t;
        }
        if(cnt==0){
           if(ans){
                printf("2\n");
           }else{
                printf("1\n");
           }
        }
        else{
            if(ans) printf("1\n");
            else printf("2\n");
        }

    }
    return 0;
}