#include<bits/stdc++.h> #include<bits/extc++.h> using namespace std; #define ll long long #define ull unsigned long long #define pii pair<int,int> #define fr first #define sc second #define mk make_pair #define pb push_back const int MAXN=2000010,N=26,Mod1=998244353,Mod2=1011451423; int read(){int x=0,f=1;char c=getchar();while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();return x*f;} int n,m;ll ans; struct node{ ll x,y; node operator*(const node&G)const{return {x*G.x%Mod1,y*G.y%Mod2};} node operator+(const node&G)const{return {x+G.x>=Mod1?x+G.x-Mod1:x+G.x,y+G.y>=Mod2?y+G.y-Mod2:y+G.y};} node operator-(const node&G)const{return {x-G.x<0?x-G.x+Mod1:x-G.x,y-G.y<0?y-G.y+Mod2:y-G.y};} bool operator<(const node&G)const{return x!=G.x?x<G.x:y<G.y;} bool operator==(const node&G)const{return x==G.x&&y==G.y;} }hs[MAXN],jc[MAXN],B;int cnt; inline ull Hsh(node G){return (ull)(G.x<<30)|G.y;} node qry(int l,int r){return hs[r]-hs[l-1]*jc[r-l+1];} int hw[MAXN]; struct trie{ __gnu_pbds::gp_hash_table<ull,int>mp; void dfs(node x){ // cout<<x.x<<" "<<mp[x]<<endl; for(char c='a';c<='z';c++)if(mp.find(Hsh(x*B+(node){c,c}))!=mp.end()){ node v=x*B+(node){c,c}; mp[Hsh(v)]+=mp[Hsh(x)]; dfs(v); } } void build(){ dfs((node){0,0}); } }S,T; char s[MAXN],t[MAXN]; pii p[MAXN];int a[MAXN]; void slv(){ S.mp.clear(),T.mp.clear(); n=read(),m=read(); for(int o=1;o<=n;o++){ scanf("%s",s+1); int k=strlen(s+1); a[o]=a[o-1]+k; reverse(s+1,s+k+1); for(int i=a[o-1]+1;i<=a[o];i++)t[i]=s[i-a[o-1]]; int mid=0,r=0; for(int i=1;i<=k;i++){ if(i<r)hw[i]=min(r-i+1,hw[mid*2-i]);else hw[i]=0; while(i+hw[i]<=k&&s[i-hw[i]]==s[i+hw[i]])hw[i]++; if(i+hw[i]-1>r)r=i+hw[i]-1,mid=i; ans+=hw[i]*m; } for(int i=1;i<=k;i++)hs[i]=hs[i-1]*B+(node){s[i],s[i]}; node tmp={0,0}; int mx=0; for(int i=1;i<=k;i++){ S.mp[Hsh(hs[i])]++; tmp=(node){s[i],s[i]}*jc[i-1]+tmp; if((i&1)&&tmp==hs[i]&&i<k)p[++cnt]=mk(a[o-1]+i,a[o]); } } S.build(); for(int o=1;o<=m;o++){ scanf("%s",s+1); int k=strlen(s+1); int mid=0,r=0; for(int i=1;i<=k;i++){ if(i<r)hw[i]=min(r-i+1,hw[mid*2-i]);else hw[i]=0; while(i+hw[i]<=k&&s[i-hw[i]]==s[i+hw[i]])hw[i]++; if(i+hw[i]-1>r)r=i+hw[i]-1,mid=i; ans+=hw[i]*n; } for(int i=1;i<=k;i++)hs[i]=hs[i-1]*B+(node){s[i],s[i]}; node tmp={0,0}; int mx=0; for(int i=1;i<=k;i++){ T.mp[Hsh(hs[i])]++; tmp=(node){s[i],s[i]}*jc[i-1]+tmp; if((i&1)&&tmp==hs[i]){ int l=i,r=k; while(l<r){ int mid=(l+r+1)>>1; if(S.mp.find(Hsh(qry(i+1,mid)))!=S.mp.end())l=mid; else r=mid-1; } if(i<l)ans+=S.mp[Hsh(qry(i+1,l))]; } } } hs[0]={0,0}; for(int i=1;i<=a[n];i++)hs[i]=hs[i-1]*B+(node){t[i],t[i]}; T.build(); for(int i=1;i<=cnt;i++){ int l=p[i].fr,r=p[i].sc; while(l<r){ int mid=(l+r+1)>>1; // cout<<p[i].fr<<" "<<mid<<" "<<qry(p[i].fr,mid).x<<endl; if(T.mp.find(Hsh(qry(p[i].fr+1,mid)))!=T.mp.end())l=mid; else r=mid-1; } // cout<<p[i].fr+1<<" "<<p[i].sc<<" "<<l<<" "<<qry(p[i].fr+1,l).x<<" "<<T.mp[qry(p[i].fr+1,l)]<<endl; ans+=T.mp[Hsh(qry(p[i].fr+1,l))]; } printf("%lld",ans); } signed main(){ // freopen("1.in","r",stdin);freopen("1.out","w",stdout); B={131,127};jc[0]={1,1}; for(int i=1;i<=MAXN-5;i++)jc[i]=jc[i-1]*B; int _=read();while(_--) slv(); //cerr<<clock()*1.0/CLOCKS_PER_SEC<<"s\n"; return 0; }