#include <algorithm>
#include <iostream>
#include <cstring>
#include <queue>
#include <assert.h>
constexpr int N(500010);
namespace trie
{
	int sz(1),pos[N];
	struct _z
	{
		int ch[26],p,dep,ptpos,es[26],pampos;
	}z[N];
	struct pam
	{
		struct _z
		{
			int fail,len,trans[26],ch[26],fa,ft[20],dep,rs[26];
		}z[N];
		int pos[N],sz,cnt;bool nc[N];char s[N];
		pam()
		{
			sz=1;z[1].fail=0;z[0].fail=1;z[1].len=-1;z[0].len=0;
			for(int i(0);i<26;++i) z[0].trans[i]=z[1].trans[i]=1,z[0].ch[i]=z[1].ch[i]=-1,z[0].rs[i]=1;
		}
		void pop()
		{
			if(nc[cnt])
			{
				z[z[pos[cnt]].fa].ch[s[cnt]-'a']=-1;
			}
			--cnt;
		}
		std::pair<int,int> push(char c,int (&es)[26])
		{
			int fa(pos[cnt++]);
			if(!(z[fa].len<cnt-1 && s[cnt-1-z[fa].len]==c)) fa=z[fa].trans[c-'a'];s[cnt]=c;
			if(!(~z[fa].ch[c-'a']))
			{
				nc[cnt]=true;++sz;pos[cnt]=sz;z[sz].fa=fa;z[sz].len=z[fa].len+2;
				int t(z[fa].trans[c-'a']);if(~z[t].ch[c-'a']) t=z[t].ch[c-'a'];else t=0;z[sz].fail=t;
				z[fa].ch[c-'a']=sz;z[sz].dep=z[t].dep+1;z[sz].ft[0]=t;
				for(int i(1);(1<<i)<=z[sz].dep;++i) z[sz].ft[i]=z[z[sz].ft[i-1]].ft[i-1];
				std::memset(z[sz].ch,0xff,sizeof(z[sz].ch));
				std::memcpy(z[sz].trans,z[t].trans,sizeof(z[sz].trans));
				z[sz].trans[s[cnt-z[t].len]-'a']=t;
			}else
			{
				nc[cnt]=false;pos[cnt]=z[fa].ch[c-'a'];
			}
			for(int i(0);i<26;++i) z[pos[cnt]].rs[i]=es[i]=z[z[pos[cnt]].trans[i]].len+2;
			int l(z[pos[cnt]].len);if(l<cnt) es[s[cnt-l]-'a']=l+2;
			return {z[pos[cnt]].len,pos[cnt]};
		}
	}T;
	void dfs(int u)
	{
		for(int i(0),v;i<26;++i) if((v=z[u].ch[i]))
		{
			auto [p,pampos]=T.push(char(i+'a'),z[v].es);
			z[v].p=p;z[v].pampos=pampos;
			dfs(v);T.pop();
		}
	}
	void build()
	{
		for(int i(0);i<26;++i) z[1].es[i]=1;
		dfs(1);
	}
}
struct bit
{
	int b[N];
	void add(int x,int v){for(;x<N;x+=(x&(-x))) b[x]+=v;}
	int _qry(int x){int ans(0);for(;x;x-=(x&(-x))) ans+=b[x];return ans;}
	int qry(int l,int r){return _qry(r)-_qry(l-1);}
}TB;
int qid[N],ans[N];
namespace pt
{
	struct _z
	{
		int dc,ps[26],id,fail,len,nd[26],dfn,ed;
		bool initialized;
		int get_id(int p){return std::lower_bound(ps,ps+dc,p)-ps;}
	}z[N];
	std::vector<int> qs[N],ts[N];
	int sz(1),dcnt;
	void build()
	{
		std::queue<std::pair<int,int>> qq;qq.push({1,1});trie::z[1].ptpos=1;z[1].id=1;
		while(!qq.empty())
		{
			auto [pn,tn]=qq.front();qq.pop();
			if(!z[pn].initialized)
			{
				z[pn].initialized=true;
				std::memcpy(z[pn].ps,trie::z[tn].es,sizeof(z[pn].ps));
				std::sort(z[pn].ps,z[pn].ps+26);z[pn].dc=std::unique(z[pn].ps,z[pn].ps+26)-z[pn].ps;
				if(pn==1)
				{
					for(int i(0);i<z[pn].dc;++i) z[pn].nd[i]=1;
				}
				else
				{
					int fl(z[z[pn].fail].len),v(trie::z[tn].pampos),f(z[pn].fail);
					for(int i(19);i>=0;--i) if((1<<i)<=trie::T.z[v].dep && trie::T.z[trie::T.z[v].ft[i]].len>=fl) v=trie::T.z[v].ft[i];
					for(int i(0);i<26;++i)
					{
						int p;
						if(trie::T.z[v].len<fl){p=trie::z[tn].es[i];}
						else{p=trie::T.z[v].rs[i];}
						int j(z[f].get_id(p));
						int w(z[f].nd[j]);
						int q(trie::z[tn].es[i]);
						z[pn].nd[z[pn].get_id(q)]=w;
					}
				}
			}
			for(int i(0);i<26;++i) if(trie::z[tn].ch[i])
			{
				int k(z[pn].get_id(trie::z[tn].es[i]));
				if(z[z[pn].nd[k]].len<=z[pn].len)
				{
					int c(++sz);
					z[c].id=trie::z[tn].ch[i];
					z[c].fail=z[pn].nd[k];
					z[c].len=z[pn].len+1;
					z[pn].nd[k]=c;
				}
				trie::z[trie::z[tn].ch[i]].ptpos=z[pn].nd[k];
				qq.emplace(z[pn].nd[k],trie::z[tn].ch[i]);
			}
		}
	}
	void dfs_d(int u){z[u].dfn=++dcnt;for(int v:ts[u]) dfs_d(v);z[u].ed=dcnt;}
	void dfs(int u)
	{
		TB.add(z[u].dfn,1);
		for(int q:qs[u])
		{
			int v(qid[q]);
			ans[q]=TB.qry(z[v].dfn,z[v].ed);
		}
		for(int i(0);i<z[u].dc;++i) if(z[z[u].nd[i]].len>z[u].len) dfs(z[u].nd[i]);
		TB.add(z[u].dfn,-1);
	}
	void calc()
	{
		for(int i(2);i<=sz;++i)
		{
			ts[z[i].fail].emplace_back(i);
		}
		dfs_d(1);
		dfs(1);
	}
}
namespace fr{
	#include <ctype.h>
	char buf[1<<23],*p1=buf,*p2=buf,obuf[1<<23],*O=obuf;
	#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
	#define putchar(c) (((O==obuf+(1<<23))?(fwrite(obuf,1,O-obuf,stdout),O=obuf):O),*O++=(c))
	void rd(char *x){char c=getchar();while(isspace(c)) c=getchar();while(!isspace(c) && c!=EOF) *(x++)=c,c=getchar();*(x++)='\0';}
	void rd(char &x){x=getchar();while(isspace(x)) x=getchar();}
	template<class T> void rd(T &x){T ret=0;bool flg=false;char c=getchar();while(!isdigit(c) && c!='-') c=getchar();
		if(c=='-') c=getchar(),flg=true;while(isdigit(c)) ret=(ret<<1)+(ret<<3)+(c-'0'),c=getchar();if(flg) x=-ret;else x=ret;}
	void pc(char c){putchar(c);}void flush(){fwrite(obuf,1,O-obuf,stdout),O=obuf;}
	template<class T> void wr(T x){if(x<0) putchar('-'),x=-x;if(x==0) putchar('0');static int cnt,stk[110];cnt=0;while(x) stk[++cnt]=x%10,x/=10;
	for(int i=cnt;i;--i) putchar(stk[i]+'0');}
}
using fr::rd;using fr::pc;using fr::wr;using fr::flush;
int main()
{
	int T,n,q;rd(T);rd(n);rd(q);
	if(T==0)
	{
		static char s[N];
		for(int i(1);i<=n;++i)
		{
			rd(s+1);int l(std::strlen(s+1)),u(1);
			for(int j(1);j<=l;++j)
			{
				if(!trie::z[u].ch[s[j]-'a']) trie::z[u].ch[s[j]-'a']=(++trie::sz);
				u=trie::z[u].ch[s[j]-'a'];
			}
			trie::pos[i]=u;
		}
	}
	else
	{
		trie::pos[0]=1;
		for(int i(1);i<=n;++i)
		{
			int fa;char sc;rd(fa);rd(sc);int id(sc-'a');
			if(!trie::z[trie::pos[fa]].ch[id]) trie::z[trie::pos[fa]].ch[id]=(++trie::sz);
			trie::pos[i]=trie::z[trie::pos[fa]].ch[id];
		}
	}
	trie::build();
	pt::build();
	static int pos[N];
	for(int i(1);i<=n;++i) pos[i]=trie::z[trie::pos[i]].ptpos;
	for(int i(1);i<=q;++i)
	{
		int u,v;rd(u);rd(v);
		qid[i]=pos[u];
		pt::qs[pos[v]].emplace_back(i);
	}
	pt::calc();
	for(int i(1);i<=q;++i) wr(ans[i]),pc('\n');flush();
	return 0;
}