#include<bits/stdc++.h>
using namespace std;
const int MAX=1e6;
int trie[MAX][30];
int sum[MAX];
int tot;
void build_trie(string s){
    int root=0;
    for(int i=0,len=s.length();i<len;i++){
        int id=s[i]-'a';
        if(trie[root][id]==0) trie[root][id]=++tot;
        root=trie[root][id];
    }
    sum[root]++;
}
void get_fail(){
    queue<int> que;
    for(int i=0;i<26;i++)
        if(trie[0][i]){fial[0][i]=0;que.push(trie[0][i]);}
    while(que.empty()){
        int now=que.front();
        que.pop();
        for(int i=0;i<26;i++)
            if(trie[now][i]) {
                que.push(trie[now][i]);
                fail[trie[now][i]]=trie[faie[now]][i];
            }
            else trie[now][i]=trie[fail[now]][i];
    }
}
int query(string s){
    int now=0;
    int ans=0;
    for(int i=0,len=s.length();i<len;i++){
        now=trie[now][s[i]-'a'
        temp=now;
        while(temp!=0) {
            ans+=sum[temp];
            temp=fail[temp];
            }
        }
    }
    return ans;
}