题目描述

汐汐和楠楠在玩游戏。她们有n堆石子，第i堆石子有a[i]个，保证初始时a[i] ≤ a[i+1]（1 ≤ i < n）。现在她们轮流对这些石子进行操作，每次操作可以选择满足a[i] > a[i-1]（a[0]视为0）的一堆石子，并从中取走一个。谁最后不能取了谁输。汐汐先手，她们都使用最优策略，请判断最后谁会取得胜利。

输入格式

本题有多组测试数据。 第一行一个正整数T，表示有T组测试数据。 对于每组测试数据： 第一行一个整数n（1 ≤ n ≤ 100），表示石子堆数。 接下来一行n个数，第i个数为a[i]（1 ≤ a[i] ≤ 10^9），意义如上所述。

输出格式

输出T行，每行对应一组测试数据，如果汐汐最后会赢输出1，否则输出2。

样例输入

3
1
1
2
1 1
3
6 8 9

样例输出

1
2
1

数据范围与提示

• 对于30%的数据：1 ≤ n ≤ 10，1 ≤ a_i ≤ 100。
• 对于100%的数据：1 ≤ T ≤ 3，1 ≤ n ≤ 100，1 ≤ a[i] ≤ 10^9。