mxgxoi1ms , qz P3699 ACzdj qwq

#include<bits/stdc++.h>
using namespace std;
int cnt[1000005],fail[1000005],n,siz;
int trie[2000005][26],ed[2000005],tot;
vector<int> edge[1000005];
char text[2000005];
inline void Add(string st){
	for(int i=0;i<st.size();i++){
		text[siz++]=st[i];
	}
	text[siz++]='&';
}
inline void insert(string st,int id){
	int pos=0;
	for(int i=0;i<st.size();i++){
		int ch=st[i]-'a';
		if(!trie[pos][ch]){
			trie[pos][ch]=++tot;
		}
		pos=trie[pos][ch];
	}
	ed[id]=pos;
}
inline void Getfail(){
	queue<int> Q;
	for(int i=0;i<26;i++){
		if(trie[0][i]){
			Q.push(trie[0][i]);
		}
	}
	while(!Q.empty()){
		int x=Q.front();
		Q.pop();
		for(int i=0;i<26;i++){
			if(trie[x][i]){
				fail[trie[x][i]]=trie[fail[x]][i];
				Q.push(trie[x][i]);
			}
			else{
				trie[x][i]=trie[fail[x]][i];
			}
		}
	}
}
inline void dfs(int pos){
	for(int i=0;i<edge[pos].size();i++){
		int to=edge[pos][i];
		dfs(to);
		cnt[pos]+=cnt[to];	
	}
}
inline void solve(){
	int pos=0;
	for(int i=0;i<strlen(text);i++){
		int ch=text[i]-'a';
		pos=trie[pos][ch];
		cnt[pos]++;
	}
	for(int i=1;i<=tot;i++){
		edge[fail[i]].push_back(i);
	}
	dfs(0);
	for(int i=1;i<=n;i++){
		cout<<cnt[ed[i]]<<endl;
	}
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		string s;
		cin>>s;
		Add(s);
		insert(s,i);
	}
	Getfail();
	solve();
	return 0;
}