#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'

const int M = 3e6 + 5, mod = 1e9 + 7;
int tr[M][66], cnt[M], tot;
int getnum(char x)
{
    if (x >= 'A' && x <= 'Z')
        return x - 'A';
    else if (x >= 'a' && x <= 'z')
        return x - 'a' + 26;
    else
        return x - '0' + 52;
}

void insert(string s)
{
    int now = 0;
    for (auto x : s)
    {
        if (!tr[now][getnum(x)])
        {
            tr[now][getnum(x)] = ++tot;
        }
        now = tr[now][getnum(x)];
        cnt[now]++;
    }
}
int query(string s)
{
    int now = 0;
    for (auto x : s)
    {
        if (!tr[now][getnum(x)])
        {
            return 0;
        }
        now = tr[now][getnum(x)];
    }
    return cnt[now];
}

void solve()
{
    tot = 0;
    int n, q;
    cin >> n >> q;
    while (n--)
    {
        string s;
        cin >> s;
        insert(s);
    }
    while (q--)
    {
        string s;
        cin >> s;
        cout << query(s) << endl;
    }
    for (int i = 0; i <= tot; i++)
    {
        cnt[i] = 0;
        for (int j = 0; j < 66; j++)
            tr[i][j] = 0;
    }
}
signed main()
{
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int t = 1;
    cin >> t;
    while (t--)
        solve();
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int M=2e5+5;
int a[M],dp[M],in[M],cn,cnt,sta[M],low[M],dfn[M],sum[M];
vector<int>f[M],ff[M];
int top,belong[M];
void dfs(int now) {
	dfn[now]=low[now]=++cn;
	sta[++top]=now;
	in[now]=1;
	for(auto to:f[now])
		if(!dfn[to])dfs(to),low[now]=min(low[now],low[to]);
		else if(in[to])low[now]=min(low[now],dfn[to]);
	if(dfn[now]==low[now]) {
		++cnt;
		int y;
		do {
			y=sta[top--];
			in[y]=0;
			sum[cnt]+=a[y];
			belong[y]=cnt;
		} while(now!=y);
	}
}
int ru[M],chu[M];
void solve() {
	int n,m;
	cin>>n>>m;
	for(int i=1; i<=n; ++i)cin>>a[i];
	while(m--) {
		int x,y;
		cin>>x>>y;
		f[x].push_back(y);
	}
	for(int i=1; i<=n; ++i)if(!dfn[i])dfs(i);
	for(int i=1; i<=n; ++i)
		for(auto to:f[i])
			if(belong[i]!=belong[to])
				ru[belong[to]]++,chu[belong[i]]++,ff[belong[i]].push_back(belong[to]);
	queue<int>p;
	for(int i=1; i<=cnt; ++i) {
		dp[i]=sum[i];
		if(ru[i]==0)p.push(i);
	}
	while(!p.empty()) {
		int t=p.front();
		p.pop();
		for(auto to:ff[t]) {
			dp[to]=max(dp[to],sum[to]+dp[t]);
			if(!--ru[to])p.push(to);
		}
	}
	int ans=0;
	for(int i=1; i<=n; ++i)ans=max(ans,dp[i]);
	cout<<ans;
}
signed main() {
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	int t=1;
	//cin>>t;
	while(t--)solve();
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'

// #define int long long
const int M = 5e6 + 5, mod = 998244353;

int c, dfn[M], low[M], head[M], cnt, belong[M];
struct dian
{
    int from, to, ne;
} f[M];
vector<int> p[M];
void add(int x, int y)
{
    f[++c].to = y;
    f[c].from = x;
    f[c].ne = head[x];
    head[x] = c;
}
void dfs(int now, int fa)
{
    dfn[now] = low[now] = ++cnt;
    for (int i = head[now]; i; i = f[i].ne)
    {
        int to = f[i].to;
        if (!dfn[to])
            dfs(to, now);
        else if (fa != to)
            low[now] = min(low[now], dfn[to]);
    }
    low[fa] = min(low[fa], low[now]);
}
vector<int> edge[M];
void dfss(int start, int now)
{
    belong[now] = start;
    for (auto x : edge[now])
    {
        if (belong[x])
            continue;
        dfss(start, x);
    }
}

void solve()
{
    int n, m, V;
    cin >> n >> m;
    // vector<int> a(n + 2);
    // for (int i = 1; i <= n; i++)
    //     cin >> a[i];
    while (m--)
    {
        int x, y;
        cin >> x >> y;
        if (x == y)
            continue;
        add(x, y);
        add(y, x);
    }
    for (int i = 1; i <= n; ++i)
        if (!dfn[i])
            dfs(i, i);
    vector<int> vis(c + 2);
    for (int now = 1; now <= n; ++now)
    {
        for (int i = head[now]; i; i = f[i].ne)
        {
            int to = f[i].to;
            if (low[to] > dfn[now])
                vis[i] = 1;
        }
    }
    set<pair<int, int>> s;
    for (int i = 1; i <= c; i += 2)
    {
        int minn = min(f[i].from, f[i].to);
        int maxx = max(f[i].from, f[i].to);
        if ((vis[i] || vis[i + 1]) && s.find({minn, maxx}) == s.end()) // 如果这条边是桥，就跳过
        {
            s.insert(make_pair(minn, maxx));
            continue;
        }
        int x = f[i].from, y = f[i].to;
        edge[x].push_back(y);
        edge[y].push_back(x);
    }
    vector<vector<int>> f(n + 2);
    for (int i = 1; i <= n; ++i)
    {
        if (!belong[i])
            dfss(i, i);
    }
    for (int i = 1; i <= n; ++i)
        f[belong[i]].push_back(i);

    int ans = 0;
    for (int i = 1; i <= n; ++i)
    {
        if (f[i].size() == 0)
            continue;
        ans++;
    }
    cout << ans << endl;
    for (int i = 1; i <= n; ++i)
    {
        if (f[i].size() == 0)
            continue;
        cout << f[i].size() << ' ';
        for (auto j : f[i])
        {
            cout << j << ' ';
        }
        cout << endl;
    }
}
signed main()
{
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int t = 1;
    // cin >> t;
    while (t--)
        solve();

    return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int M=1e5+5;
int len,n,m,a[M],belong[M],sum,ans[M],cnt,l[M],r[M],c[M];
void fun() {
	len=sqrt(n),cnt=(n-1)/len+1;
	for(int i=1; i<=cnt; ++i)l[i]=r[i-1]+1,r[i]=len*i;
	r[cnt]=n;
	for(int i=1; i<=cnt; ++i)
		for(int j=l[i]; j<=r[i]; ++j)belong[j]=i;
}
struct dian {
	int l,r,id;
} f[M];
bool operator<(dian a,dian b) {
	return (belong[a.l] ^ belong[b.l]) ? belong[a.l] < belong[b.l] : ((belong[a.l] & 1) ? a.r < b.r : a.r > b.r);
}
void add(int x) {
	sum-=c[a[x]]*c[a[x]];
	c[a[x]]++;
	sum+=c[a[x]]*c[a[x]];
}
void dele(int x) {
	sum-=c[a[x]]*c[a[x]];
	c[a[x]]--;
	sum+=c[a[x]]*c[a[x]];
}
signed main() {
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	int k;
	cin>>n>>m>>k;
	int l=1,r=0;
	for(int i=1; i<=n; ++i)cin>>a[i];
	fun();
	for(int i=1; i<=m; ++i)cin>>f[i].l>>f[i].r,f[i].id=i;
	sort(f+1,f+1+m);
	for(int i=1; i<=m; ++i) {
		while(l>f[i].l)add(--l);
		while(r<f[i].r)add(++r);
		while(l<f[i].l)dele(l++);
		while(r>f[i].r)dele(r--);
		ans[f[i].id]=sum;
	}
	for(int i=1; i<=m; ++i)cout<<ans[i]<<'\n';
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
#define int long long 
#define lc now<<1
#define rc now<<1|1
const int M=1e5+5;
struct dian{
	int l,r,sum,add;
}f[M<<2|1];
int a[M];
void pushup(int now){
	f[now].sum=f[lc].sum+f[rc].sum;
}
void build(int now,int l,int r){
	f[now]={l,r,a[l],0};
	if(l==r)return ;
	int mid=l+r>>1;
	build(lc,l,mid);
	build(rc,mid+1,r);
	pushup(now);
}
void pushdown(int now){
	if(f[now].add){
		f[lc].sum+=(f[lc].r-f[lc].l+1)*f[now].add;
		f[rc].sum+=(f[rc].r-f[rc].l+1)*f[now].add;
		f[lc].add+=f[now].add;
		f[rc].add+=f[now].add;
		f[now].add=0;
	} 
}
void modi(int now,int x,int y,int k){
	if(x<=f[now].l&&y>=f[now].r){
		f[now].sum+=(f[now].r-f[now].l+1)*k;
		f[now].add+=k;
		return;
	}
	pushdown(now);
	int mid=f[now].l+f[now].r>>1;
	if(x<=mid)modi(lc,x,y,k);
	if(y>mid)modi(rc,x,y,k);
	pushup(now);
}
int que(int now,int x,int y){
	if(x<=f[now].l&&y>=f[now].r)
		return f[now].sum;
	int mid=f[now].l+f[now].r>>1;
	pushdown(now);
	int sum=0;
	if(x<=mid)sum+=que(lc,x,y);
	if(y>mid)sum+=que(rc,x,y);
	return sum;
}
signed main(){
	ios::sync_with_stdio(false),cin.tie(0);
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;++i)
	cin>>a[i];
	build(1,1,n);
	while(m--){
		int op,x,y,k;
		cin>>op;
		if(op==1){
			cin>>x>>y>>k;
			modi(1,x,y,k);
		}
		else {
			cin>>x>>y;
			cout<<que(1,x,y)<<'\n';
		}
	}
	return 0;
}