String Farm

Sanggeun and Seonyeong run a rather unusual farm. Most farms raise animals or grow vegetables, but they raise strings.

A string is a sequence of consecutive characters. Whenever a string grows, a single character is appended only to its left end or its right end. Existing characters are never removed, and no character is ever inserted into the middle of a string.

The two of them photographed their strings as they grew. Unfortunately, they wrote nothing on the photos, so they forgot which photo shows which string. Now they want to hang the photos on a wall in the order the strings grew.

Each photo can be described by a single string. A sequence of photos $s_1, s_2, \dots, s_k$ must obey the following rule: for photo $s_i$ to come immediately before photo $s_{i+1}$, string $s_{i+1}$ must be a grown form of $s_i$; that is, $s_i$ must be a contiguous substring of $s_{i+1}$. They never take the same photo twice, so all photos used in a sequence are distinct.

Given the photos they took, write a program that finds the largest number of photos that can be lined up while obeying the rule.

The input consists of several test cases.

The first line of each test case contains the number of photos $N$ ($1 \le N \le 10^4$). Each of the next $N$ lines contains the string on one photo. Each string consists of lowercase letters only and has length at most $1000$.

Within a single test case, the sum of the lengths of all given strings does not exceed $10^6$.

The last line of the input contains a single $0$, which marks the end of the input.

For each test case, print on its own line the length of the longest sequence of photos that can be arranged according to the rule.