【题目描述】
Tony和Mary中午吃完饭后闲着无聊，决定玩游戏打发时间。HIZ100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
两人商量之后决定了游戏规则如下：HIZ100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
1、 初始时有n堆火柴HIZ100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
2、 两人轮流取火柴HIZ100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
3、 每次可以从最多m堆中取走任意多个，但取走火柴的总数必须大于0HIZ100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
4、 谁无法取火柴了（即没有火柴了）谁就输了HIZ100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
Tony和Mary都是无敌聪明的人，所以两人每次取火柴时都不会犯错误。HIZ100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
但火柴的数量实在是太多了，Tony决定编个程序自动帮他取，你帮帮他吧。HIZ100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
【输入】
第一行一个整数T(T<=10)，表示数据个数HIZ100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
解下来包括T组数据，每组数据第一行两个整数n,m（n<=500，m<=100）HIZ100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
之后n行，每行一个整数ai（ai<=10^50），描述某一行的火柴数HIZ100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
【输出】
按输入顺序对每一组数据输出答案。HIZ100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
若Tony和Mary肯定会输，则输出一个数0；否则输出1HIZ100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
【输入样例】
2
2 1
10
11
2 1
10000
10000
【输出样例】
1
0
