#include "bits/stdc++.h"
using namespace std;
const int maxn = 300300;
int trie[maxn][3], nd = 1;
char str[44];
int value[maxn], stp[maxn];
int dp[44][44];
int ok(int l, int r){
	if(l == r) return 1;
	if(l + 1 == r && str[l] == str[r]) return 1;
	if(l + 1 == r) return 0;
	if(dp[l][r] != -1) return dp[l][r];
	int v = ok(l + 1, r - 1);
	if(v == 0) return dp[l][r] = 0;
	if(str[l] == str[r]) return dp[l][r] = 1;
	return dp[l][r] = 0;
}
int count(){
	memset(dp, -1, sizeof(dp));
	int len = strlen(str);
	int ans = 0;
	for(int e = 0; e < len; e++)
		for(int f = e; f < len; f++)
			ans += ok(e, f);
	return ans;
}
//Tested
template<typename T, bool fastQuery = true> class sparse_table{
private:
    vector<vector<T> > table;
    int size, lg;
    void build(){
        for(int bit = 1; bit < lg; bit++)
            for(int ptr = 0; ptr + (1<<bit) <= size; ptr++)
                table[bit][ptr] = table[bit-1][ptr] + table[bit-1][ptr + (1<<(bit-1))];
    }
public:
    sparse_table(int size){
        assert(size > 0);
        this->size = size;
        lg = log2(size) + 2;
        table.assign(lg, vector<T>(size));
    }
    sparse_table(vector<T> & initial){
        *this = sparse_table(initial.size());
        for(int e = 0; e < size; e++)
            table[0][e] = initial[e];
        build();
    }
    T get(int from, int to){
        assert(from <= to);
        T ans = T();
        if(fastQuery){
            int nLG = __builtin_clz(1) - __builtin_clz(to - from + 1);
            ans = table[nLG][from] + table[nLG][to - (1<<nLG) + 1];
        } else {
            for(int e = lg-1; e >= 0; e--)
                if((to + 1 - from)&(1<<e)){
                    ans = ans + table[e][from];
                    from += 1<<e;
                }
        }
        return ans;
    }
};
struct to_rm{
	int ind, v;
	to_rm(){

	}
	to_rm(int a, int b){
		ind = a;
		v = b;
	}
	to_rm operator + (to_rm other){
		if(v < other.v) return other;
		if(v > other.v) return * this;
		if(ind < other.ind) return * this;
		return other;
	}
};
int main(){
	int cs;
	scanf("%d", &cs);
	while(cs--){
		int n, q;
		scanf("%d %d", &n, &q);
		nd = 1;
		for(int e = 0; e < 3; e++) trie[0][e] = 0;
		for(int e = 0; e < n; e++){
			scanf("%s", str);
			value[e] = count();
			int cur = 0;
			for(int f = 0; str[f]; f++){
				int & v = trie[cur][str[f]-'a'];
				if(v == 0){
					for(int g = 0; g < 3; g++) trie[nd][g] = 0;
					v = nd++;
				}
				cur = v;
			}
			// cout <<e  << " " << value[e] << endl;
			stp[cur] = e;
		}
		vector<to_rm> lol;
		for(int e = 0; e < n;e++) lol.push_back(to_rm(e, value[e]));
		sparse_table<to_rm> sss(lol);
		for(int e = 0; e < q; e++){
			char s1[44], s2[44];
			int l, r;
			scanf("%s %s", s1, s2);
			int cur = 0;
			for(int f = 0; s1[f]; f++){
				cur = trie[cur][s1[f]-'a'];
			}
			l = stp[cur];
			cur = 0;
			for(int f = 0; s2[f]; f++){
				cur = trie[cur][s2[f]-'a'];
			}
			r = stp[cur];
			if(l > r) swap(l, r);
			// cout << l << " " << r << endl;
			printf("%d\n", sss.get(l, r).ind + 1);
		}
	}
	return 0;
}