温馨提示：请注意你代码的空间常数。

给定一个长为 $n$ 的非负整数序列 $a$，和一个常数 $x$。

你需要把 $a$ 划分成若干段，使得「每一段的按位与」的按位或 $\leq x$。

你需要最大化划分成的段数，或者报告无解。

输入格式

本题有多组数据。第一行一个正整数 $T$（$1\leq T\leq 10^4$）表示数据组数。对于每组测试数据：

第一行输入两个正整数 $n,m$（$1\leq n,m,n\cdot m\leq 4\cdot 10^6$），其中 $m$ 的作用如下：

为了减少读入量，序列 $a$ 和常数 $x$ 以 $32$ 进制的方式输入。具体的，给出的是长度恰好为 $m$ 的，只包含数字 $0\sim 9$ 和小写字母 $a\sim v$ 的字符串（$a$ 代表 $10$，$b$ 代表 $11$，以此类推，可能有前导 $0$），其真实值即为该字符串转换为 $32$ 进制得到的数。显然这样输入的数 $\in [0,32^m)$。

第二行以上述方式输入常数 $x$。

第三行以上述方式输入序列 $a$，相邻字符串之间恰有一个空格隔开。

保证 $\sum n\cdot m\leq 2\cdot 10^7$。

输出格式

对于每组数据，若有解，则输出最大的划分出的段数；若无解，输出 $-1$。

样例

输入

3
4 1
2
3 1 4 2
1 3
lct
sam
3 1
t
6 h c

输出

2
-1
2