Cut Check Bit

Problem Description

温馨提示：请注意你代码的空间常数。 给定一个长为 $n$ 的非负整数序列 $a$，和一个常数 $x$。 你需要把 $a$ 划分成若干段，使得「每一段的按位与」的按位或 $\le x$。 你需要最大化划分成的段数，或者报告无解。

Input

本题有多组数据。第一行一个正整数 $T$（$1\le T\le10^4$）表示数据组数。对于每组测试数据： 第一行输入两个正整数 $n,m$（$1\le n,m,n\cdot m\le4\cdot 10^6$），其中 $m$ 的作用如下： 为了减少读入量，序列 $a$ 和常数 $x$ 以 $32$ 进制的方式输入。具体的，给出的是长度恰好为 $m$ 的，只包含数字 $\texttt{0}\sim\texttt{9}$ 和小写字母 $\texttt{a}\sim\texttt{v}$ 的字符串（$\texttt{a}$ 代表 $10$，$\texttt{b}$ 代表 $11$，以此类推，可能有前导 $\texttt{0}$），其真实值即为该字符串转换为 $32$ 进制得到的数。显然这样输入的数 $\in[0,32^m)$。 第二行以上述方式输入常数 $x$。 第三行以上述方式输入序列 $a$，相邻字符串之间恰有一个空格隔开。 保证 $\sum n\cdot m\le2\cdot10^7$。

Output

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

Sample Input

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

Sample Output

2
-1
2

Source

2025“钉耙编程”中国大学生算法设计暑期联赛（10）