题目描述

小田是一个著名的探险家，正在一个远古的遗迹进行探险，正当她想要继续深入遗迹时，一个大门挡住了她的去路，大门上需要输入相应的密码才能进去，且密码每一位只有两种状态。她通过丰富的探险经验，发现了大门周边的墙壁上有着密码的提示信息。墙壁上有着多串数列，墙壁的壁画提示说在一串数列中的每一个数字任意放符号+或 -，这样就可以构成一个表达式，也就可以计算出表达式的值。这样可以排列组合出来多个表达式，每个表达式的值都有可能不同，如果其中某一个数值能够被 $k$ 整除的话，那这个数列就是能够被 $k$ 整除的，现在墙壁上有多串数列，如果当前数列能够被整除，那对应的密码位置的值就为$1$，否则就为$0$。

现在小田请求你的帮助，计算出相应的密码打开这个遗迹的大门。

输入格式

第一行一个整数 $M$，表示有多少串数列。

对于每串数列：

第一行两个整数 $n$ 和 $k$，$n$ 表示数列中整数的个数。

第二行 $n$ 个整数，表示输入数列 $\{a_n\}$。

输出格式

输出应有 $M$ 行，第$i$个数就是第$i$个数列能否被$k$整除的结果，如果可以，则输出$1$ ，否则输出$0$。

样例 #1

样例输入 #1

2
4 7
17 5 -21 15
4 5
17 5 -21 15

样例输出 #1

1
0

提示

样例输入输出 1 解释

对于整数数列：$17,5,-21,-15$，可以构造出 $8$ 个表达式：

• $17+5+(-21)+15=16$
• $17+5+(-21)-15=-14$
• $17+5-(-21)+15=58$
• $17+5-(-21)-15=28$
• $17-5+(-21)+15=6$
• $17-5+(-21)-15=-24$
• $17-5-(-21)+15=48$
• $17-5-(-21)-15=18$

该数列能被 $7$ 整除（$17+5+(-21)-15=-14$），但不能被 $5$ 整除。

所以相应的，第一个数列是输出$1$，第二个数列输出$0$

数据规模与约定

对于全部的测试点，保证 $1 \le n \le 10^4,2 \le k \le 100,\left| a_i \right| \le 10^4$。