#include<bits/stdc++.h>
using namespace std;
#define md(a) a=(a%mod+mod)%mod
#define file(a) freopen(#a".in","r",stdin);freopen(#a".out","w",stdout)

bool ST;

const int N=1000005,B=5e5,P1=36634229,mod1=998244353;
int pw1[N*2];
int Test,n,Q,Ans[N],qx[N],qy[N];char str[N],s[N*2];vector<int>inc[N],qry[N];
bool vst[N];int all,t,st[N],top,lim[N*2];vector<int>req[N];

const int M=19491001;
struct Hash_Table
{
	int h[M],st[M],top,tot,val[N*2],f[N*2],nxt[N*2];
	inline void ins(int v)
	{
		int x=v%M;
		for(int k=h[x];k;k=nxt[k])if(val[k]==v){f[k]++;return ;}
		tot++;if(!h[x])st[++top]=x;f[tot]=1,val[tot]=v,nxt[tot]=h[x],h[x]=tot;
	}
	inline int ask(int v)
	{
		int x=v%M;
		for(int k=h[x];k;k=nxt[k])if(val[k]==v)return f[k];
		return 0;
	}
	inline void Clear()
	{
		while(top)h[st[top]]=0,top--;tot=0;
	}
}Map;

int il1[N],dl1[N],ha1[N];
inline void ad1(int&x,int y){x+=y;if(x>=mod1)x-=mod1;}
inline void de1(int&x,int y){x-=y;if(x<0)x+=mod1;}
int scc=0;
struct num
{
	int m,len,h1n;vector<int>f;
	inline void read(int id)
	{
		cin>>(str+1);m=strlen(str+1);s[0]=' ';
		for(int i=1;i<m;i++)s[++len]=str[i],s[++len]='#';s[++len]=str[m];f.resize(len+1);
		for(int i=1,p=0,mid=0;i<=len;i++)
		{
			if(i<=p)f[i]=min(p-i+1,f[mid*2-i]);
			while(i-f[i]>=1&&i+f[i]<=len&&s[i-f[i]]==s[i+f[i]])f[i]++;
			if(i+f[i]-1>p)p=i+f[i]-1,mid=i;
		}
		if(m<B)inc[m].push_back(id);
		// for(int i=1;i<=len;i++)cout<<f[i]<<' ';cout<<'\n';
	}
	inline void gethash()
	{
		h1n=0;
		for(int i=1;i<=len;i++)
		{
			int a=f[i];if(a>=lim[i])a=5e6+1;
			// cout<<a<<'\n';
			h1n=(1ll*h1n*P1+a)%mod1;
		}
	}
	inline void up(int l,int r,int st,int v)
	{
		if(l>r||r<1||l>m)return ;if(l<1)st+=(1-l)*2,l=1;if(r>m)r=m;
		// cout<<"up:"<<l<<' '<<r<<' '<<st<<' '<<v<<'\n';
		ad1(il1[l],1ll*pw1[st]*v%mod1),ad1(dl1[r],1ll*pw1[st+(r-l)*2]*v%mod1);
	}
	inline void Run()
	{
		// for(int i=all;i<=len;i+=2)
		// {
		// 	int hs=0;
		// 	for(int t=1,p=i-all+1;t<=all;t++,p++)
		// 	{
		// 		int a=f[p];if(a>=lim[t])a=5e6+1;
		// 		hs=(1ll*hs*P1+a)%mod1;
		// 	}
		// 	Map.ins(hs);
		// }return ;
		int l1=0,r1=0,l2=0,r2=0;
		l1=0,r1=(t-1)/2,l2=r1+1,r2=t-1;
		// cout<<l1<<' '<<r1<<' '<<l2<<" "<<r2<<'\n';
		// for(int i=1;i<=m;i++)cout<<il1[i]<<' ';cout<<'\n';
		// for(int i=1;i<=m;i++)cout<<dl1[i]<<' ';cout<<'\n';
		for(int i=1;i<=len;i+=2)
		{
			int x=(i+1)/2,d=(f[i]-1)/2,p=0;if(!f[i])d=-1;
			p=min(d,r1-l1);up(x+l1,x+p,l1*2,5e6+1),up(x+p+1,x+r1,(p+1)*2,f[i]);
			p=min(d,r2-l2);up(x+r2-p,x+r2,(r2-p)*2,5e6+1),up(x+l2,x+r2-p-1,l2*2,f[i]);
		}
		l1=0,r1=t/2-1,l2=r1+1,r2=t-2;
		// cout<<l1<<' '<<r1<<' '<<l2<<" "<<r2<<'\n';
		for(int i=2;i<=len;i+=2)
		{
			int x=i/2+1,d=f[i]/2-1,p=0;
			// cout<<x<<" "<<p<<'\n';
			p=min(d,r1-l1);up(x+l1,x+p,l1*2+1,5e6+1),up(x+p+1,x+r1,(p+1)*2+1,f[i]);
			p=min(d,r2-l2);up(x+r2-p,x+r2,(r2-p)*2+1,5e6+1),up(x+l2,x+r2-p-1,l2*2+1,f[i]);
		}
		// for(int i=1;i<=m;i++)cout<<il1[i]<<' ';cout<<'\n';
		// for(int i=1;i<=m;i++)cout<<dl1[i]<<' ';cout<<'\n';
		for(int i=1,h1=0;i<=m;i++)
		{
			h1=1ll*h1*pw1[2]%mod1;
			ad1(h1,il1[i]);
			ad1(ha1[i],h1);
			de1(h1,dl1[i]);
		}
		for(int i=1;i<=m;i++)if(i>=t)
		{
			Map.ins(ha1[i]);
			// cout<<ha1[i]<<' ';
		}
		// cout<<'\n';
		for(int i=1;i<=m;i++)il1[i]=dl1[i]=ha1[i]=0;
	}
}a[N];

inline void Run(int id)
{
	// cout<<"run:"<<id<<'\n';
	a[id].Run();
	for(int qid:req[id]){int x=qx[qid];Ans[qid]=Map.ask(a[x].h1n);}
	Map.Clear(),req[id].clear();
}

inline void calc()
{
	for(int id:inc[t])for(int qid:qry[id])
	{
		int y=qy[qid];req[y].push_back(qid);
		if(!vst[y])st[++top]=y,vst[y]=1;
	}all=t*2-1;if(!top)return ;
	for(int i=1;i<=all;i++)lim[i]=min(i,all-i+1);for(int id:inc[t])a[id].gethash();
	while(top)Run(st[top]),vst[st[top]]=0,top--;
}

inline void calc2(int id)
{
	t=a[id].m;
	for(int qid:qry[id])
	{
		int y=qy[qid];req[y].push_back(qid);
		if(!vst[y])st[++top]=y,vst[y]=1;
	}all=t*2-1;if(!top)return ;
	for(int i=1;i<=all;i++)lim[i]=min(i,all-i+1);a[id].gethash();
	while(top)Run(st[top]),vst[st[top]]=0,top--;
}

bool ED;

signed main()
{
	cerr<<(&ST-&ED)/1024.0/1024<<endl;ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	// file(match);
	pw1[0]=1;for(int i=1;i<N*2;i++)pw1[i]=1ll*pw1[i-1]*P1%mod1;
	cin>>Test>>n>>Q;for(int i=1;i<=n;i++)a[i].read(i);
	for(int i=1;i<=Q;i++){int x,y;cin>>x>>y;qx[i]=x,qy[i]=y;if(a[x].m<=a[y].m)qry[x].push_back(i);}
	for(int i=1;i<B;i++)t=i,calc();for(int i=1;i<=n;i++){if(a[i].m>=B)calc2(i);}
	for(int i=1;i<=Q;i++)cout<<Ans[i]<<'\n';
	return 0;
}