#include<cstdio>
#include<cctype>
#include<vector>
#include<cstring>
#include<algorithm>

#define lowbit(k) (k&(-k))

#define maxn 505505

template<class T>

inline T read(){
	T r=0,f=0;
	char c;
	while(!isdigit(c=getchar()))f|=(c=='-');
	while(isdigit(c))r=(r*10)+(c^48),c=getchar();
	return f?-r:r;
}

inline char getc(){
	char c;
	while(!isalpha(c=getchar()));
	return c;
}

char str[maxn];

int n,m,num[maxn],ans[maxn];

namespace ACAM{

	int tot,id[maxn],dep[maxn],fail[maxn],tr[maxn][26];

	int size[maxn],val[maxn][26],ch[maxn][26];

	int s_dfn,dfn[maxn],low[maxn];

	std::vector<int> to[maxn];

	void DFS(int u){
		dfn[u]=++s_dfn;
		for(auto v:to[u])DFS(v);
		low[u]=s_dfn;
	}

	void dfs(int u);

	inline void build();

}

namespace ExPAM{

	int tot,ed,top,id[maxn],num[maxn],len[maxn];

	int anc[maxn][22],ch[maxn][26],trans[maxn][26];

	std::vector<std::pair<int,int> > to[maxn];

	void dfs(int u,int p){
		id[u]=p;
		for(auto P:to[u]){
			bool flg=0;
			int v=P.first;
			int c=P.second;
			str[++top]=c+'a';
			int fa=num[u];
			if(str[top]!=str[top-len[fa]-1])
				fa=trans[fa][c];
			if(ch[fa][c])num[v]=ch[fa][c];
			else {
				flg=1,num[v]=++tot;
				len[tot]=len[fa]+2;
			    anc[tot][0]=ch[trans[fa][c]][c];
				for(int i=0;i<26;i++)trans[tot][i]=trans[anc[tot][0]][i];
				for(int i=1;i<=18;i++)anc[tot][i]=anc[anc[tot][i-1]][i-1];
				trans[tot][str[top-len[anc[tot][0]]]-'a']=anc[tot][0];
				ch[fa][c]=tot;
			}
			auto &valp=ACAM::val[p];
			int pos=std::lower_bound(valp,valp+ACAM::size[p],len[num[v]])-valp;
			if(!ACAM::tr[p][pos]){
				int nxt=++ACAM::tot;
				ACAM::dep[nxt]=top;
				ACAM::id[nxt]=num[v];
				ACAM::tr[p][pos]=nxt;
				int C=str[top-len[num[v]]]-'a';
				static std::pair<int,int> tmp[33];
				for(int i=0;i<26;i++)
					tmp[i]={(i^C?len[trans[num[v]][i]]:len[num[v]])+2,i};
				std::sort(tmp,tmp+26);
				for(int i=0;i<26;i++){
					if(i&&tmp[i].first==tmp[i-1].first)continue;
					int size=ACAM::size[nxt]++;
					ACAM::val[nxt][size]=tmp[i].first;
					ACAM::ch[nxt][size]=tmp[i].second;
				}
			}
			dfs(v,ACAM::tr[p][pos]),top--;
			if(flg)ch[fa][c]=0;
		}
	}

	inline void build(){
		str[0]='?';
	    len[++tot]=-1;
		for(int i=0;i<=18;i++)
			anc[0][i]=anc[1][i]=1;
		for(int i=0;i<26;i++)
			trans[0][i]=trans[1][i]=1;
		ACAM::size[0]=1;
		ACAM::val[0][0]=1;
		num[0]=1,dfs(0,0);
	}

}

inline void ACAM::build(){
	static int hd,tl,q[maxn];
	for(int i=0;i<26;i++)
		if(tr[0][i])q[++tl]=tr[0][i];
	while(hd^tl){
		int u=q[++hd],f=fail[u],p=id[u];
		to[f].push_back(u);
		static int trans[26];
		if(ExPAM::len[p]<dep[f]){
			for(int i=0;i<size[u];i++)
				trans[i]=i;
		}
		else {
			for(int i=18;~i;i--)
				if(ExPAM::len[ExPAM::anc[p][i]]>=dep[f])
					p=ExPAM::anc[p][i];
			for(int i=0;i<size[u];i++){
				int len=ExPAM::len[ExPAM::trans[p][ch[u][i]]]+2;
				trans[i]=std::lower_bound(val[f],val[f]+size[f],len)-val[f];
			}
		}
		for(int i=0;i<size[u];i++){
			if(!tr[u][i]){
				tr[u][i]=tr[f][trans[i]];
				continue;
			}
			else {
				q[++tl]=tr[u][i];
				fail[tr[u][i]]=tr[f][trans[i]];
			}
		}
	}
	DFS(0);
}

namespace BIT{

	int c[maxn];

	inline void add(int k,int x){
		for(;k<=ACAM::tot+1;k+=lowbit(k))c[k]+=x;
	}

	inline int ask(int k){
		int Sum=0;
		for(;k;k^=lowbit(k))Sum+=c[k];
		return Sum;
	}

}

std::vector<std::pair<int,int> > ask[maxn];

void ACAM::dfs(int u){
	BIT::add(dfn[u],1);
	for(auto P:ask[u]){
		int rt=P.first;
		ans[P.second]=BIT::ask(low[rt])-BIT::ask(dfn[rt]-1);
	}
	for(int i=0;i<26;i++)
		if(dep[tr[u][i]]==dep[u]+1)dfs(tr[u][i]);
	BIT::add(dfn[u],-1);
}

int main(){
	int type=read<int>();
	n=read<int>(),m=read<int>();
    if(!type){
		int tot=0;
	    for(int i=1;i<=n;i++){
			scanf("%s",str+1);
			int len=strlen(str+1),p=0;
			for(int i=1;i<=len;i++)
				ExPAM::to[p].push_back({++tot,str[i]-'a'}),p=tot;
			num[i]=p;
		}
		n=tot;
	}
	else {
		for(int i=1;i<=n;i++){
			num[i]=i;
			int f=read<int>();
			ExPAM::to[f].push_back({i,getc()-'a'});
		}
	}
	ExPAM::build();
	ACAM::build();
	for(int i=1;i<=m;i++){
		int x=ExPAM::id[num[read<int>()]];
		int y=ExPAM::id[num[read<int>()]];
		ask[y].push_back({x,i});
	}
	ACAM::dfs(0);
	for(int i=1;i<=m;i++)
		printf("%d\n",ans[i]);
	return 0;
}