【题目描述】

Tony和Mary中午吃完饭后闲着无聊，决定玩游戏打发时间。

两人商量之后决定了游戏规则如下：

• 1、 初始时有 $n$ 堆火柴;
• 2、 两人轮流取火柴;
• 3、 每次可以从最多 $m$ 堆中取走任意多个，但取走火柴的总数必须大于0 ;
• 4、 谁无法取火柴了（即没有火柴了）谁就输了。

Tony和Mary都是无敌聪明的人，所以两人每次取火柴时都不会犯错误。

但火柴的数量实在是太多了，Tony决定编个程序自动帮他取，你帮帮他吧。

【输入格式】

第一行一个整数 $T \ (T \le 10)$ ，表示 $T$ 组数据。每组数据描述如下：

第一行两个整数 $n \ m \ (n \le 500，m \le 100)$。

下来 $n$ 个整数 $a_i \ (1 \le a_i \le 10^{50})$，描述某一行的火柴数。

【输出格式】

按输入顺序对每一组数据输出答案。 若Tony和Mary肯定会输，则输出一个数 0；否则输出 1。

【样例输入】

2
2 1
10
11
2 1
10000
10000

【样例输出】

1
0