cultivando o odio

#include <bits/stdc++.h>
#define MAX 10007
#define ALPHA 26

using namespace std;

struct node{
    struct node* word[ALPHA];
    struct node* link;
    bool end, mark;
    int id;
    vector<int> travel;

    node() {
        fill(word, word+ALPHA, (node*)0);
        travel.clear();
        link = (node*)0;
        end = false;
        mark = false;
        id = -1;
    }
};

node* head;

int ans[MAX], biggest[MAX];
vector<string> palavras;

bool compare(string a, string b) {
    return a.size() < b.size();
}

void add(string s, int id){
    node* current = head;
    //int biggest = 0;

    for(int i = 0; i < s.size(); i++){
        int letra = s[i]-'a';

        if(!current->word[letra]) current->word[letra] = new node();

        //if(current->word[letra]->end) biggest = max(biggest, ans[current->word[letra]->id]);

        current->word[letra]->travel.push_back(id);
        current = current->word[letra];
    }
    current->end = true;
    current->id = id;
    //ans[id] += biggest;
}

void bfs(){
    queue<node*> q;

    for(int i = 0; i < ALPHA; i++){
        if(head->word[i]){
            head->word[i]->link = head;
            q.push(head->word[i]);

            if(head->word[i]->end){
                //cout << "ola = " << head->word[i]->id << "\n";

                //cout << head->word[i]->id << " ->> " << ans[head->word[i]->id] << endl;
                ans[head->word[i]->id] += biggest[head->word[i]->id];
                //cout << head->word[i]->id << " ->> " << ans[head->word[i]->id] << endl;

                for(int j = 0; j < head->word[i]->travel.size(); j++){
                    //cout << head->word[i]->travel[j] << endl;
                    biggest[head->word[i]->travel[j]]++;
                }
            }
        } else head->word[i] = head;
    }

    while(!q.empty()){
        node* pai = q.front();
        q.pop();

        for(int i = 0; i < ALPHA; i++){
            if(pai->word[i]){
                node* filho = pai->link;
                while(!filho->word[i]) filho = filho->link;
                filho = filho->word[i];
                pai->word[i]->link = filho;

                while(!filho->end && filho->id != 0) filho = filho->link;

                q.push(pai->word[i]);
                //cout << pai->word[i]->id << " : " << filho->id << endl;
                if(filho->end){
                    //cout << "filho prodigo = " << filho->id << " (local = " << pai->word[i]->id << ")\n";
                    for(int j = 0; j < pai->word[i]->travel.size(); j++){
                        //cout << pai->word[i]->travel[j] << endl;
                        biggest[pai->word[i]->travel[j]] = max(ans[filho->id], biggest[pai->word[i]->travel[j]]);
                    }
                }

                if(pai->word[i]->end){
                    //cout << "fim = " << pai->word[i]->id << "\n";


                    //cout << pai->word[i]->id << " ->> " << ans[pai->word[i]->id] << endl;
                    ans[pai->word[i]->id] += biggest[pai->word[i]->id];
                    //cout << pai->word[i]->id << " ->> " << ans[pai->word[i]->id] << endl;

                    for(int j = 0; j < pai->word[i]->travel.size(); j++){
                        biggest[pai->word[i]->travel[j]] = max(ans[pai->word[i]->id], biggest[pai->word[i]->travel[j]]);
                        //cout << pai->word[i]->travel[j] << " >>-- " << biggest[pai->word[i]->travel[j]]<< endl;
                    }
                }
            }
        }
    }
}
int main(){
    while(true){
        int qnt; cin >> qnt;
        if(!qnt) break;

        for(int i = 0; i <= MAX; i++) {
            ans[i] = 1;
            biggest[i] = 0;
        }
        head = new node();
        head->id = 0;
        for(int i = 1; i <= qnt; i++){
            string s; cin >> s;
            //palavras.push_back(s);
            add(s, i);
        }
        //sort(palavras.begin(), palavras.end(), compare);

        bfs();
        int resp = 0;
        for(int i = 0; i <= qnt; i++) resp = max(ans[i], resp);
        cout << resp << endl;
    }
    return 0;
}