题目描述

Tony 和 Mary 中午吃完饭后闲着无聊，决定玩游戏打发时间。 两人商量之后决定了游戏规则如下：

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

Tony 和 Mary 都是无敌聪明的人，所以两人每次取火柴时都不会犯错误。但火柴的数量实在是太多了，Tony 决定编个程序自动帮他取，你帮帮他吧。

输入格式

第一行一个整数 $T~(T \leq 10)$，表示数据个数。

接下来包括 $T$ 组数据，每组数据第一行两个整数 $n,m~(n \leq 500,m \leq 100)$ 之后n行，每行一个整数 $a_i~(a_i \leq 10^{50})$，描述某一行的火柴数。

输出格式

按输入顺序对每一组数据输出答案。

若 Tony 和 Mary 肯定会输，则输出一个数 $0$；否则输出 $1$。

2
2 1
10
11
2 1
10000
10000

1
0