当前没有测试数据。

Description

Tony和Mary中午吃完饭后闲着无聊，决定玩游戏打发时间。 两人商量之后决定了游戏规则如下： 1、 初始时有n堆火柴 2、 两人轮流取火柴 3、 每次可以从最多m堆中取走任意多个，但取走火柴的总数必须大于0 4、 谁无法取火柴了（即没有火柴了）谁就输了 Tony和Mary都是无敌聪明的人，所以两人每次取火柴时都不会犯错误。 但火柴的数量实在是太多了，Tony决定编个程序自动帮他取，你帮帮他吧。

Input

第一行一个整数T(T<=10)，表示数据个数 解下来包括T组数据，每组数据第一行两个整数n,m（n<=500，m<=100） 之后n行，每行一个整数ai（ai<=10^50），描述某一行的火柴数

Output

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

Samples

2
2 1
10
11
2 1
10000
10000

1
0