#include<bits/stdc++.h> #include<bits/extc++.h> #define pii pair<int,int> #define mk make_pair using namespace std; const int N=2e6+10,base=131,ibs1=190839696,ibs2=526717562,mod1=1e9+7,mod2=1e9+9; mt19937_64 rng(9517); int XOR=rng(); struct myhash{ int operator() (const pii a)const{ return (a.first+a.second)^XOR; } }; __gnu_pbds::gp_hash_table<pii,int,myhash> M; int d[N],pib1[N],pib2[N],ha1[N],ha2[N]; string s[N],t[N]; int n,m; struct Trie{ int trie[N][26];int tot=1; int cnt1[N],cnt2[N];pii hsh[N]; void insert(string s,int op){ if(op==1) reverse(s.begin(),s.end()); int now=1,H1=0,H2=0; for(auto ch:s){ H1=(1ll*H1*base+ch)%mod1; H2=(1ll*H2*base+ch)%mod2; int o=ch-'a'; if(!trie[now][o]) trie[now][o]=++tot; now=trie[now][o];hsh[now]=mk(H1,H2); //cout<<now<<' '<<hsh[now]<<' '<<op<<endl; if(op==1) cnt1[now]++;else cnt2[now]++; } } void pdfs(int x){ /*if(x!=1){ //cout<<hsh[x]<<' '<<cnt1[x]<<endl; if(cnt1[x]) m1[hsh[x]]=cnt1[x]; if(cnt2[x]) m2[hsh[x]]=cnt2[x]; }*/ for(int i=0;i<26;i++){ if(trie[x][i]){ cnt1[trie[x][i]]+=cnt1[x]; cnt2[trie[x][i]]+=cnt2[x]; pdfs(trie[x][i]); } } } void dfs1(int x){ if(x!=1){ if(cnt1[x]) M[hsh[x]]=cnt1[x]; } for(int i=0;i<26;i++){ if(trie[x][i]) dfs1(trie[x][i]); } } void dfs2(int x){ if(x!=1){ if(cnt2[x]) M[hsh[x]]=cnt2[x]; } for(int i=0;i<26;i++){ if(trie[x][i]) dfs2(trie[x][i]); } } }T; int calc(string s,int op){ if(op==2) reverse(s.begin(),s.end()); int len=s.length(); for(int i=1;i<=len;i++) d[i]=0; s=' '+s+'/'; int L=1,R=0; for(int i=1;i<=len;i++){ if(i<=R) d[i]=min(d[L+R-i],R-i); while(s[i-d[i]]==s[i+d[i]]){ if(i+d[i]>R) L=i-d[i],R=i+d[i]; d[i]++; }d[i]--; } long long ans=0; for(int i=1;i<=len;i++) ans+=d[i]+1; if(op==1) ans*=m;else ans*=n; //stage 1 //cout<<s<<' '<<op<<endl; pib1[0]=1,pib2[0]=1;int pw1=1,pw2=1; for(int i=1;i<=len;i++){ pib1[i]=1ll*pib1[i-1]*ibs1%mod1; pib2[i]=1ll*pib2[i-1]*ibs2%mod2; ha1[i]=(ha1[i-1]+1ll*pw1*s[i])%mod1; ha2[i]=(ha2[i-1]+1ll*pw2*s[i])%mod2; pw1=1ll*pw1*base%mod1; pw2=1ll*pw2*base%mod2; } for(int i=1;i<=len;i++){ if(i+d[i]==R&&i-d[i]!=1){ int pos=i-d[i]-1; int l=1,r=pos+1; while(l<r){ int mid=(l+r)/2; int H1=1ll*(ha1[pos]+mod1-ha1[mid-1])*pib1[mid-1]%mod1; int H2=1ll*(ha2[pos]+mod2-ha2[mid-1])*pib2[mid-1]%mod2; //cout<<mid<<' '<<pos<<' '<<H<<endl; //cout<<m1.count(H^XOR)<<' '<<l<<' '<<r<<endl; bool flg=0; if(op==1) flg=(M.find(mk(H1,H2))!=M.end());//cout<<flg<<' '<<op<<' '<<s<<endl; else flg=(M.find(mk(H1,H2))!=M.end()); //cout<<flg<<endl; if(flg) r=mid;else l=mid+1; } int H1=1ll*(ha1[pos]+mod1-ha1[l-1])*pib1[l-1]%mod1; int H2=1ll*(ha2[pos]+mod2-ha2[l-1])*pib2[l-1]%mod2; //cout<<l<<' '<<pos<<' '<<H<<endl; if(H1||H2) if(op==1) ans+=M[mk(H1,H2)];else ans+=M[mk(H1,H2)]; } } //stage 2 return ans; } void slv(){ cin>>n>>m; for(int i=1;i<=n;i++) cin>>s[i]; for(int i=1;i<=m;i++) cin>>t[i]; for(int i=1;i<=n;i++) T.insert(s[i],1); for(int i=1;i<=m;i++) T.insert(t[i],2); T.pdfs(1); /*for(int i=1;i<=n;i++){ int h=0; for(int j=0;j<s[i].length();j++){ h=(1ll*h*base+s[i][j]); m1[h^XOR]+=j+1; } } for(int i=1;i<=m;i++){ int h=0; for(int j=0;j<t[i].length();j++){ h=(1ll*h*base+t[i][j]); m2[h^XOR]+=j+1; } }*/ //calc("jrmzidkrkdizmzidkrxd"); long long ans=0; T.dfs2(1); for(int i=1;i<=n;i++) ans+=calc(s[i],1); M.clear();T.dfs1(1); for(int i=1;i<=m;i++) ans+=calc(t[i],2); cout<<ans<<endl; } int main(){ //freopen("str.in","r",stdin); //freopen("str.out","w",stdout); int t;cin>>t; while(t--) slv(); return 0; }