一开始感觉完全不可做，因为记忆中线性基求出来以后，只能知道异或和为0的子集数量。然后去补了线性基有关的知识，最后1h知道怎么做了。

题意：

思路：

设题目给定的集合为\(S\)，大小为\(n\)，\(S\)的线性基大小为\(k\)，如果一个数\(x\)能被\(S\)的线性基表示，一定有\(2^{(n-k)}\)个\(S\)的子集异或和等于\(x\)。
口胡一下证明：因为线性基能够表示\(x\)，那么在\(n-k\)个不属于线性基的元素中任意选择，设他们的异或和为\(y\)，显然\(y\oplus x\)也能被线性基表示，那么每一个选择都有且仅有一个对应的线性表示，那么不同的选择个数就是答案，即\(2^{(n-k)}\)
这样就可以得到一个做法：只要知道有多少个\(x\in [l,r]\)，能被线性表示就行了。暴力枚举的时间复杂度\(O(TNM2^{250})\)，寄。
这类计数有一种很常见的trick，设\(f(x)\)为小于等于\(x\)的数有多少个能被线性表示，那么\((f(r)-f(l-1))*2^{n-k}\)即为答案。
现在只需要知道\(f(x)\)怎么求，因为线性基中的数二进制最高位互不相同，那么从高到低枚举二进制位即可维护答案，维护的过程类似数位\(dp\)。
举个例子：当前枚举到第\(k\)位，\(x_k=1\)，之前线性表示出来的数为\(y\)，\(y_k=1\)，如果线性基中有最高位为\(k\)的元素，那么考虑是否选择这个元素：如果选择，\(y_k=0\)，因为\(y\)肯定小于\(x\)了，那么接下来线性基中的元素就随便选了，有\(m\)个的话就有\(2^m\)种方案；如果不选择就继续。
用bitset处理异或和，总的时间复杂度\(O(TMN^2/64)\)。

AC Code:

// Problem: GG and YY's Binary Number
// Contest: HDOJ
// URL: https://acm.hdu.edu.cn/showproblem.php?pid=7364
// Memory Limit: 262 MB
// Time Limit: 12000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;

#define fr first
#define se second
#define et0 exit(0);
#define rep(i, a, b) for(int i = (int)(a); i <= (int)(b); i ++)
#define rrep(i, a, b) for(int i = (int)(a); i >= (int)(b); i --)
#define IO ios::sync_with_stdio(false),cin.tie(0);

typedef long long LL;
typedef pair<int, int> PII;
typedef unsigned long long ULL;
 
const int INF = 0X3f3f3f3f, N = 250 + 10, MOD = 1e9 + 7;
const double eps = 1e-7, pi = acos(-1);

int n, p[N], ex;
int pow2[N], pre[N];

int idx;

bitset<N> a[N], b[N];

void init() {
	pow2[0] = 1;
	rep (i, 1, N - 1) pow2[i] = (pow2[i - 1] << 1ll) % MOD;
}

void insert(bitset<N> x) {
	rrep (i, 249, 0) {
		if (x[i] & 1) {
			if (!p[i]) {
				p[i] = ++idx;
				b[idx] = x;
				return;
			}
			x ^= b[p[i]];
		}
	}
}


int calc(string &t, int len) {
	if (t[0] == '-') return 0;
	
	int start = -1;
	bitset<N> x;
	x.reset();
	rep (i, 0, len - 1) {
		if (t[i] == '1') {
			start = i;
			break;
		}
	}
	if (start == -1) return 1;
	
	int ut = start, ret = 0, ok = 1, st = 0; // ok：最后的线性表示出的x是否需要算进答案；st：x是否是空集
	rrep (i, len - 1 - start, 0) {
		if (t[ut] == '1') {
			if (x[i] & 1) {
				if (p[i]) {
					ret = (1ll * ret + 1ll * pow2[pre[i] - 1] % MOD) % MOD;
				}
			}
			else {
				int k = pre[i] - (p[i] ? 1 : 0);
				ret = (1ll * ret + 1ll * pow2[k] % MOD) % MOD;
				if (!st) ret = (1ll * ret - 1 + MOD) % MOD;
				if (p[i]) x ^= b[p[i]], st = 1;
				else {
					ok = 0;
					break;
				}
			}
		}
		else {
			if (x[i] & 1) {
				if (p[i]) {
					x ^= b[p[i]];
					st = 1;
				}
				else {
					ok = 0;
					break;
				}
			}
		}
		
		ut++;
	}	
	
	if (ok) ret = ((1ll * ret + 1) % MOD + (st ? 1 : 0)) % MOD;
	else ret = (1ll * ret + 1) % MOD;

	return ret;
}

void work() {
	idx = 0;
	rep (i, 0, 249) p[i] = 0;
	
	int q;
    cin >> n >> q;
    rep (i, 1, n) {
    	string x;
    	cin >> x;
    	a[i].reset();
    	int xl = x.length();
    	rep (j, 0, xl - 1) if (x[xl - 1 - j] == '1') a[i][j] = 1;
    	insert(a[i]);
    }
    ex = pow2[n - idx];
    
	if (p[0]) pre[0] = 1;
	else pre[0] = 0;
    rep (i, 1, 249) {
    	if (p[i]) pre[i] = pre[i - 1] + 1;
    	else pre[i] = pre[i - 1];
    }
    
    while (q--) {
    	int ok = 1;
    	string l, r;
    	cin >> l >> r;
    	int lenl = l.length(), lenr = r.length();
    	rrep (i, lenl - 1, 0) {
    		if (l[i] == '1') {
    			l[i] = '0';
    			ok = 0;
    			break;
    		}
    		else l[i] = '1';
    	}
    	if (ok) l = "-1";
    	int res = ((1ll * calc(r, lenr) - calc(l, lenl)) * ex % MOD + MOD) % MOD;
    	cout << res << "\n";
    }
}
/*

*/

signed main() {
    IO
    init();
    
    int test = 1;
	cin >> test;
    while (test--) work();
    
    return 0;
}