LG3966

#include<bits/stdc++.h>

using namespace std;

#define gc c=getchar()
#define r(x) read(x)
#define ll long long

template<typename T>
inline void read(T&x){
    x=0;T k=1;char gc;
    while(!isdigit(c)){if(c=='-')k=-1;gc;}
    while(isdigit(c)){x=x*10+c-'0';gc;}x*=k;
}

const int N=1e6+207;

namespace Suffix_Array{
    int n,m;

    int SA[N];
    int Rank[N];
    int tmp[N];
    int cnt[N];

    inline void Qsort(int *a,int *b){
        for(int i=1;i<=m;++i)cnt[i]=0;
        for(int i=1;i<=n;++i)cnt[a[i]]++;
        for(int i=1;i<=m;++i)cnt[i]+=cnt[i-1];
        for(int i=n;i>=1;--i)SA[cnt[a[b[i]]]--]=b[i];
    }

    inline void GetSA(int *s,int len){
        n=len,m=300;
        for(int i=1;i<=n;++i)Rank[i]=s[i];
        for(int i=1;i<=n;++i)tmp[i]=i;
        Qsort(Rank,tmp);
        for(int l=1,p=0;p<n;l<<=1){
            p=0;
            for(int i=1;i<=l;++i)tmp[++p]=n-i+1;
            for(int i=1;i<=n;++i)if(SA[i]>l)tmp[++p]=SA[i]-l;
            Qsort(Rank,tmp);
            memcpy(tmp+1,Rank+1,n<<2);
            p=Rank[SA[1]]=1;
            for(int i=2;i<=n;++i){
                if(tmp[SA[i]]!=tmp[SA[i-1]]||tmp[SA[i]+l]!=tmp[SA[i-1]+l])++p;
                Rank[SA[i]]=p;
            }
            m=p;
        }
    }

    int Hight[N];

    inline void GetHight(int *s){
        for(int i=1,p=0;i<=n;++i){
            int j=SA[Rank[i]-1];
            if(p)--p;
            while(s[i+p]==s[j+p]&&p<n)++p;
            Hight[Rank[i]]=p;
        }
    }

    int st[N][20];
    int LG[N];

    inline void RMQinit(){
        for(int i=1;i<=n;++i)st[i][0]=Hight[i];
        for(int i=2;i<=n;++i)LG[i]=LG[i>>1]+1;
        for(int i=1;i<=LG[n];++i){
            for(int j=1;j+(1<<i)-1<=n;++j){
                st[j][i]=min(st[j][i-1],st[j+(1<<(i-1))][i-1]);
            }
        }
    }

    inline int lcp(int l,int r){
        int x=LG[r-l];
        return min(st[l+1][x],st[r-(1<<x)+1][x]);
    }

    inline int query(int x,int len){
        x=Rank[x];
        /*
        int l=x,r=x+1;
        while(Hight[l]>=len)--l;
        while(Hight[r]>=len)++r;--r;
        return r-l+1;
        */

        int l=1,r=x,mid,ans=x,ret=0;
        while(l<=r){
            mid=(l+r)>>1;
            if(lcp(mid,x)>=len)r=mid-1,ans=mid;
            else l=mid+1;
        }
        ret+=x-ans;
        ans=l=x,r=n;
        while(l<=r){
            mid=(l+r)>>1;
            if(lcp(x,mid)>=len)l=mid+1,ans=mid;
            else r=mid-1;
        }
        ret+=ans-x;
        return ret+1;

    }
}

char str[N];
int s[N];
int pos[N];
int len[N];

int main(){
    int n,p=0;r(n);
    for(int i=1;i<=n;++i){
        scanf("%s",str);
        pos[i]=p+1;
        len[i]=strlen(str);
        for(int j=0;j<len[i];++j){
            s[++p]=str[j]-'a'+1;
        }
        s[++p]=26+i;
    }
    Suffix_Array::GetSA(s,p);
    Suffix_Array::GetHight(s);
    Suffix_Array::RMQinit();
    for(int i=1;i<=n;++i){
        printf("%d\n",Suffix_Array::query(pos[i],len[i]));
    }
}