#include<bits/stdc++.h>
#define L(i, j, k) for(int i = (j); i <= (k); ++i) 
#define R(i, j, k) for(int i = (j); i >= (k); --i) 
#define ll long long 
#define vi vector < int > 
#define sz(a) ((int) (a).size()) 
#define me(a, x) memset(a, x, sizeof(a)) 
#define ull unsigned long long 
#define u128 __uint128_t 
using namespace std;
const int N = 1 << 20, T = 1 << 19, M = N * 20;
const int mod = 1019260817, G = 19491001;

int frt;
struct V {
	int val, sum;
	inline V (int VAL = 0, int SUM = 0) {
		val = VAL, sum = SUM;
	}
} seg[M];
inline V operator + (V a, V b) {
	return V((ll) a.val * b.val % mod, (a.sum + (ll) a.val * b.sum % mod) % mod);
}

int ch[M][2], tot;
void upd(int x) {
	seg[x] = seg[ch[x][0]] + seg[ch[x][1]];
}

void build(int &x, int L, int R) {
	x = ++tot;
	if(L == R) return seg[x] = V(G, 0), void(); 
	int mid = (L + R) >> 1;
	build(ch[x][0], L, mid), build(ch[x][1], mid + 1, R); upd(x);
}

void add(int &x, int L, int R, int p, int w) {
	int u = ++tot;
	ch[u][0] = ch[x][0], ch[u][1] = ch[x][1], seg[u] = seg[x], x = u;
	if(L == R) return seg[x] = V(G, w), void();
	int mid = (L + R) >> 1; 
	p <= mid ? add(ch[x][0], L, mid, p, w) : add(ch[x][1], mid + 1, R, p, w); upd(x);
}
V query(int x, int L, int R, int l, int r) {
	if(l <= L && R <= r) return seg[x];
	int mid = (L + R) >> 1;
	if(l <= mid && mid < r) 
		return query(ch[x][0], L, mid, l, r) + query(ch[x][1], mid + 1, R, l, r);
	return l <= mid ? query(ch[x][0], L, mid, l, r) : query(ch[x][1], mid + 1, R, l, r);
}

struct node {
	int pc, len;
	node (int PC = 0, int LEN = 0) {
		pc = PC;
		len = LEN;
	}
} ;

bool operator < (node a, node b) {
	int lcp = 0, len = min(a.len, b.len);
	R(j, 18, 0) { 
		int xl = lcp + (1 << j);
		if(xl <= len && 
			query(a.pc, 0, T - 1, a.len - xl, a.len - 1).sum == 
			query(b.pc, 0, T - 1, b.len - xl, b.len - 1).sum) lcp = xl;
	}
	if(lcp == len) {
		if(b.len == lcp) return false;
		else return true;
	} else {
		return query(a.pc, 0, T - 1, a.len - lcp - 1, a.len - lcp - 1).sum < 
			   query(b.pc, 0, T - 1, b.len - lcp - 1, b.len - lcp - 1).sum;
	}
}

int TP, n, q;
string s[N];
string S[N]; 

int ff[N];
int find(int x) {
	return ff[x] == x ? x : ff[x] = find(ff[x]);
}

int col[N], mp[N];

int qx[N], qy[N];
vi qry[N];
vi nxt[N], lst[N]; 
vector < node > rt[N];
int f[N];

map < int, int > mmp[N];

namespace hw {
	int n, p, ch[N][26], f[N], len[N];
	int ns[N];
	char s[N]; 
	int getfa(int x) {
		for(; p < len[x] + 1 || s[p - len[x] - 1] != s[p]; x = f[x]) ;
		return x;
	}
	int lst, tot = 1; 
	void ins() {
		lst = getfa(lst);
		if(!ch[lst][s[p] - 'a']) 
			++tot, f[tot] = ch[getfa(f[lst])][s[p] - 'a'], ch[lst][s[p] - 'a'] = tot, 
			len[tot] = len[lst] + 2;
		lst = ch[lst][s[p] - 'a'];
	}
	int main() {
		L(i, 0, tot) 
			me(ch[i], 0), f[i] = len[i] = 0;
		tot = 1, lst = 0;
		f[0] = 1, len[1] = -1;
		L(i, 1, n) p = i, ins(), ns[i] = len[lst];
		return 0;
	}
}

int hsh[N];

void solve1() {
	L(t, 1, q) {
		int x = qx[t], y = qy[t];
		if(mmp[x].count(y)) {
			cout << mmp[x][y] << '\n';
			continue;
		}
		int ns = 0;
		L(i, sz(s[x]) - 1, sz(s[y]) - 1) {
			int hsw = query(rt[y][i].pc, 0, T - 1, i - sz(s[x]) + 1, i).sum;
			if(hsw == hsh[x]) {
				ns += 1;
			}
		}
		cout << (mmp[x][y] = ns) << '\n';
	}
}

void solve2() {
	
}

int main() {
	ios :: sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> TP >> n >> q;
	assert(TP == 0);
	build(frt, 0, T - 1);
	L(i, 1, n) 
		cin >> s[i], lst[i].resize(sz(s[i])), nxt[i].resize(sz(s[i])), rt[i].resize(sz(s[i]));
	L(i, 1, q) {
		cin >> qx[i] >> qy[i];
		qry[qy[i]].emplace_back(qx[i]);
	}
	L(i, 1, n) { 
		hw :: n = sz(s[i]);
		L(j, 0, sz(s[i]) - 1) hw :: s[j + 1] = s[i][j];
		hw :: main();
		L(j, 0, sz(s[i]) - 1) ff[j] = j;
		L(j, 0, sz(s[i]) - 1) ff[j] = ff[j - hw :: ns[j + 1] + 1];
		L(j, 0, sz(s[i]) - 1) mp[ff[j]] = -1;
		int cur = frt;
		L(j, 0, sz(lst[i]) - 1) {
			if(mp[ff[j]] != -1) 
				add(cur, 0, T - 1, mp[ff[j]], j - mp[ff[j]]);
			rt[i][j] = node(cur, j + 1), mp[ff[j]] = j;
		}
		hsh[i] = query(cur, 0, T - 1, 0, sz(s[i]) - 1).sum; 
	}
	
	int xlen = 0, as = 1;
	L(i, 1, n) 
		xlen += sz(s[i]), as &= sz(s[i]) == sz(s[1]);
	if(xlen <= 1000 || q == 1 || as) 
		return solve1(), 0;
	
	assert(false);
	return 0;
}